Finding $k$-th element in prefix of size $i$

I misunderstood the original premise that A does not need to change. If you want a solution for that, a good one is to just apply the worst-case linear time selection algorithm on the original array for 0-i. This is O(i).

Assume A = [1, 0, 3, 5, 4, 7, 2, 1, 3] (inserted in that order)

There is a trivial solution to the problem at hand, and that is to store the data as so:

1
0 1
0 1 3
0 1 3 5
0 1 3 4 5
0 1 3 4 5 7
0 1 2 3 4 5 7
0 1 1 2 3 4 5 7
0 1 1 2 3 3 4 5 7

This is O(n^2) space and preprocessing, but is O(1) retrieval. It is very fast and simple, and honestly the best solution.

In order to achieve "subquadratic preprocessing", you can store this matrix type array in a sparse manner:

1,2
0,0
3,2
    0 1 3
5,4
4,3
7,5
    0 1 3 4 5 7
2,3
1,2
3,5
    0 1 1 2 3 3 4 5 7

This is O(nlog(n)) preprocessing and O(nlog(n)) space, but O(log(n)) time. You choose the gaps by computing floor(log(n)) (or ceil it does not matter) and then fill in the gaps with the elements deleted and the index that they were deleted from in the bigger array (not the smaller one). When searching given an i and k, compute ceil(i/floor(log(n))) to determine which array to start from, and then delete items from that array (do not copy it, as that will make this algorithm O(n)). When you delete an item to the right of your k, you do nothing. Delete an item to the left, and just increment your k to the next undeleted spot. By keeping track of where the last deleted item was you'll never have to traverse the array. Finally, when you reach your i, the k will be pointing to the answer. At this point, just unwind and reinsert the deleted values back in to the array.

Example with i = 7, k = 6:

Start with 0 1 1 2 3 3 4 5 7, with k pointing at 6
Delete at index 5, increment k: 0 1 1 2 3 _ 4 5 7 k=7, i=8
Delete at index 2, increment k: 0 1 _ 2 3 _ 4 5 7 k=8, i=7
i=i that we started at, so we return A[8] which is 7, and now unwind:
0 1 1 2 3 _ 4 5 7
0 1 1 2 3 3 4 5 7

This next solution was the one I was working on when I came up with the above solution (which I think is the best given the constraints). I will leave it in case if someone finds a use for it.

This solution is overly complicated for minimal gains, but matches the "subquadratic preprocessing" constraint. It is also O(n^2) space but is O(nlog(n)) preprocessing. It is O(log(n)) time.

Lets look at this problem in the simple i = n case: we need a data structure that is responsive to updates and can solve the selection problem fast. Here is such a data structure (sorted array for reference):

     1,1
  /       \
0,0       3,3
         /   \
       2,2   5,3
       /    /   \
     1,1  4,2   7,1
          /
        3,1

[0, 1, 1, 2, 3, 3, 4, 5, 7]

Let's say you want to find what was at index 2: start at 1,1 at the top; 1 < 2 so now you subtract 1 from the index you were searching for, and go to the right child. 3 > 1, so you go to the left child, and don't change your current index value. Same goes for 2,2, until you reach 1,1, which is at index 1 + 1 which is 2.

This structure is a binary tree that stores each value and its position relative to the nearest parent that it the right child of. This allows you to insert an item and have the changes be reflected across nodes you haven't touched during the insert. For example, if you insert -1 right now, which becomes 0s left child, you need to touch 1 and 0, and update their positions to 2 and 1 respectively. This automatically shifts everything to the right of 1 rightwards one as well. You can even balance this tree; just make sure to update the new parent by subtracting its left parent's value from it's value.

Now to solve the general case: instead of storing just one index, we store:

A number representing its position in the original A
A list of "previous indices" that the item was at in the sorted arrays

You build this tree just as you build a normal binary tree, except that every time you touch a node, you update it's relative position at that "time" i. Here is an example tree with a small array

A = [1, 0, 3, 5]

    1,0[0,1,1,1]
   /       \
0,1[0]     3,2[1,1]
              \
             5,3[1]

You find the kth index at "time" i by traversing the tree just as above, except you subtract the index you're looking for from the stored index at that node, then index into the list. Instead of going out of bounds, the list also stores the most recent entry. When you add a new entry, you fill in the most recent value for all i up to where you just inserted. If the i you're looking for exceeds the i stored at that node, just use the value at the array index 0 of the node and compare it to the index you're looking for (this only happens if you balance the tree). If this sounds familiar, it's because this is a type of union-set data structure.

For the above tree, finding i = 2, k = 2, you start at the top, subtract your i from 1s i, getting 2 - 0 = 2 and checking it's array at 2, which gives you 1. This is too small, so we subtract the k that we found from our k giving us 1, and move right. Next we encounter 3, we subtract our i = 2 - 2 = 0 and check the array at index 0 giving us 1 which matches our k, which is the answer.

Overly complex solution, but does manage to satisfy the requirements. Additionally, it can actually handle A changing! Balancing the tree is costly, however.


Is the following Greedy algorithm to generate Gray Codes always correct?

Your construction results in the standard binary-reflected Gray code, a recursive construction of which is described on Wikipedia, for example. We can also describe it in a different way: to generate the $m$'th codeword from the $(m-1)$'th, flip the least significant 1 bit of $m$. For example, when $n=3$, we have:
$$
\begin{array}{c|c}
000 & 000 \\
00\textbf{1} & 00\textbf{1} \\
0\textbf{1}1 & 0\textbf{1}0 \\
01\textbf{0} & 01\textbf{1} \\
\textbf{1}10 & \textbf{1}00 \\
11\textbf{1} & 10\textbf{1} \\
1\textbf{0}1 & 1\textbf{1}0 \\
10\textbf{0} & 11\textbf{1}
\end{array}
$$


Reducing from a Turing machine that recognizes is regular to the halting problem

Here's the key: work out what $L(M_2)$ is.

Notice that $M_2$ takes a string $x$ as input, so we are trying to identify which strings $x$ will cause $M_2$ to accept.

There are two cases:

Case 1: If $M$ accepts on input $w$.  Then  $L(M_2)=\Sigma^*$.

In other words, in this case, it doesn't matter what $x$ is.  $M_2$ will always accept on input $x$.  If $x$ has the form $0^n 1^n$, then $M_2$ accepts (in step 1).  If $x$ does not have the form $0^n 1^n$, then $M_2$ also accepts (in step 2).  $M_2$ accepts either way; it accepts on every possible input.
Case 2: If $M$ does not accept on input $w$.  Then $L(M_2) = \{0^n 1^n : n \in \mathbb{N}\}$.

Let's look at why this is.  If $x$ has the form $0^n 1^n$, then $M_2$ accepts in step 1.  If $x$ does not have the form $0^n 1^n$, then $M_2$ runs step 2 and doesn't accept (since $M$ doesn't accept on input $w$).

So, $L(M_2)$ is one of two possibilities: it is either $\Sigma^*$ (everything) or $\{0^n 1^n : n \in \mathbb{N}\}$.  Which of those two possibilities it is will depend upon $M$ and on $w$ (and in particular on whether $M$ accepts on $w$).  Remember that implicitly $M_2$ is dependent upon $M$ and $w$: it's got them hard-coded into its code.

Moreover, $\Sigma^*$ is regular, but $\{0^n 1^n : n \in \mathbb{N}\}$ is not regular.  So if we have a way to tell whether the language of a TM is regular or not, we have a way to tell whether $L(M_2)$ is $\Sigma^*$ or $\{0^n 1^n : n \in \mathbb{N}\}$ -- which in turn means we have a way to distinguish Case 1 from Case 2, or in other words, we have a way to tell whether $M$ accepts on input $w$ or not.

That means, if we have a way to tell whether the language of a TM is regular or not, we have a way to solve the halting problem.  (It's not the same TM; it's a related TM.  The way we tell whether $M$ accepts on $w$ is not by analyzing whether the language of $M$ is regular; we construct some new TM that is related to $M$ and $w$ in a crazy way, and then test whether the language of that new TM is regular or not.)

It's important to remember that $w$ is not an input to $M_2$.  Instead, $w$ is just a constant that is hard-coded into the source code of $M_2$.  It would be like hard-coding the value of pi as 3.1415927 in your code, except here the hardcoded constant is going to be whatever $w$ is.  Each different $w$ corresponds to a different $M_2$.

P.S. I'll also repeat a crucial point from Karolis Juodelė: "Strings are not regular, languages are."


Why is the Mean Time To Failure of multiple disks calculated via division and not multiplication?

Think of it this way. A single disk fails on average after $100,000$ hours. Now you have $100$ disks. How long before one of them fails? It will almost certainly take much less than $100,000$ hours for the first to fail, and much more than $100,000$ hours for the last to fail. (This of course depends on the distribution of failures, which is assumed to be exponential here.)

Here is another example: if you keep throwing one die, it will show $6$ after an average of $6$ throws. Now suppose that you throw two dice. How long do you expect to wait until some $6$ shows up? Certainly less than $6$ throws. (In fact, $36/11 \approx 3.27$ throws on average.)

In the second example, you need both disks to fail in order for data loss to occur. Not only this, but you also want both failure "events" to be within $10$ hours of each, since otherwise the system will recover after repairing the faulty disk. Hopefully the book explains the calculation somewhere, if not, the book is useless and you should tell your instructor to use a different one (perhaps with less pictures but more content, and not $n$th edition, prepared to finance the publisher's new yacht).


Wikipedia says this grammar is LR(0), but Grammophone says it is not; is it?

Before applying the LR algorithm to a grammar, the grammar must be "augmented" by adding the rule

$S' \to S \$$

where $S$ is the original start symbol and $S'$ and $\$$ are symbols not in the grammar. $S'$ becomes the start symbol for the augmented grammar, and the string to be parsed is augmented by appending a $\$$ at the end. A reduce action for this newly added rule is written as "accept", which has the side effect of terminating the parse.

The table shown in the Wikipedia article is for the augmented grammar, as you can see from its parsing table, which includes "accept" actions and the $\$$ end marker symbol.

For whatever reason, Grammophone does not augment grammars before applying the LR(0) algorithm. The grammar is augmented for the other algorithms. (I would call this a bug, but it could argued that it is an idiosyncratic interpretation of the algorithm.) If you give it an augmented grammar, then you get roughly the same LR(0) table as is found in Wikipedia (although an extra state is produced prior to the accept action.)

Grammophone has other issues. I don't recommend relying on it for grammar analysis.


Complexity of Matrix Inversion when $n-2$ Eigenvalues are the same

If the matrix has two distinct eigenvalues, you can find them using power iteration.

Let $\lambda_1,\lambda_2$ be the 2 eigenvalues, where $|\lambda_1| > |\lambda_2|$.  Then you can use power iteration to find $\lambda_1$.  Next, set $A' = A - \lambda_1 \text{Id}$.  $A'$ is a symmetric matrix with eigenvalues $\lambda_2,0$, so power iteration on $A'$ reveals $\lambda_2$.

The running time depends on the exact values of $\lambda_1,\lambda_2$; power iteration converges geometrically with ratio $|\lambda_2|/|\lambda_1$, so if $|\lambda_2$ is sufficiently smaller than $|\lambda_1$, you can obtain a very precise estimate with a fairly small number of iterations; if they are very close, power iteration will be ineffective.

I don't know how to generalize this handle a matrix with three distinct eigenvalues.


Complexity of finding a majority element

Let us denote the running time of your algorithm on arrays of size $n$ by $T(n)$. Then
$$
T(n) = \begin{cases}
T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(n), & \text{if } n > 2, \\
O(1), & \text{if } n \leq 2.
\end{cases}
$$
The master theorem now shows that $T(n) = O(n\log n)$.

Here is an $O(n)$ algorithm:

find-majority-element(A):
  n = len(A)
  if n = 0:
    return "none"
  if n is odd:
    y = last element of A
    if y is a majority element:
      return y
    A' = A with last element removed
    x = find-majority-element(A')
    if x is a majority element:
      return x
    otherwise:
      return "none"
  partition A into m = n/2 pairs (a_1,b_1),...,(a_m,b_m)
  construct an array B consisting of all a_i such that a_i = b_i
  x = find-majority-element(B)
  if x is a majority element:
    return x
  otherwise:
    return "none"

Clearly if there is no majority element, the algorithm returns "none". Now suppose that $x$ is a majority element. We will show that the algorithm returns $x$. We will do this by proving the following claim by induction on $n=\mathrm{len}(A)$:

  If $A$ contains a majority element $x$, then find-majority-element($A$) returns $x$.

Suppose first that $n=2m+1$ is odd, so that $x$ appears at least $m+1$ times. If $x$ is the last element, then find-majority-element($A$) will return it. Otherwise, $x$ is a majority element of $A'$ as well, and so find-majority-element($A'$) will return $x$, causing find-majority-element($A$) to return it as well.

We can now assume that $n = 2m$ is even. Suppose that $B$ contains $k$ many $x$'s and $\ell$ many other elements. We can upper-bound the number of copies of $x$ in $A$ by $2k + (n-2k-2\ell)/2 = m + k - \ell$. On the other hand, the number of copies is at least $m+1$, and so $k > \ell$. In other words, $x$ is a majority element in $B$ as well. Therefore find-majority-element($B$) will return $x$, causing `find-majority-element($A$) to return it as well.

Denoting by $T(n)$ the maximum running time of the procedure on arrays of length at most $n$, we get the recurrence
$$
T(n) \leq \begin{cases}
O(1), & \text{if } n = 0, \\
T(n-1) + O(n), & \text{if $n$ is odd}, \\
T(n/2) + O(n), & \text{if $n$ is even},
\end{cases}
$$
whose solution is $T(n) = O(n)$.


Prove key of leaf is larger or smaller than key of parent if leaf is largest key in smaller tree or smallest in larger tree with respect to parent

In Order traversal sorts key in an ascending order. If $u$ is the parent of leaf $v$ then $v$ is either left or right child of $u$. If $v$ is left child then $key[v]\leq key[u]$ which implies $key[v]$ is the largest key in the tree smaller than $key[u]$. Similar intuition follows if $v$ is right child.


Is Finding A Hitting Set of Size n/2 NP-Hard?

I think the easiest way is to reduce

  $ VC_{n/2}=\{G∣G=(V,E) $ has a vertex cover of size $|V(G)|/2\}.$ ( https://cs.stackexchange.com/a/90487/72705)

to

$ HS_{n/2}=\{(S,F)∣\exists H\subseteq S: $$H$ is a HS of $F$ of size at most $|S|/2 $$\}$.

In  https://cs.stackexchange.com/a/90487/72705 , they show that $VC_{n/2}$ is $NP$-hard.

Now, we reduce $VC_{n/2}$ to $HS_{n/2}$, which is the standard reduction from normal $VC$ to $HS$:

$S = V$
$F = E$, where $E:= \{e_1,e_2,\ldots,e_m\}$ with $e_i = \{v_j, v_k\}$ and $v_j, v_k \in V$

Clearly, this reduction can be done in poly. time and is correct, as one element in $F$ corresponds to one edge in $E$, so the HS can be mapped one to one to the vertex cover set and vice versa.

As you can see, the vertex cover set has the same number of elements as the corresponding hitting set (if there exists one). Also, $|S| = |V|$. Therefore, the Vertex Cover Set of size $|V|/2$ gives a HS of size $|S|/2$. To get a HS of size $(|S|/2) -1$, one could add two completely new elements $\alpha, \beta$ to $S$ (let this be $S'$) without changing $F$. Therefore, $\alpha$ and $\beta$ will never be in the HS of $F$, but the Hitting Set now has a size of $|S|/2 = (|S'| -2) / 2 = (|S'|/2) -1$.


Compute sum of edges in paths from source to target node?

A simple approach that should work w/out need for a hash table is as follows:
Let two boolean arrays $a,b$ such that

$a[u] =1 $ iff a path $1 \ldots u$ exists

$b[u] =1$ if a path $u  \ldots i$ exists

Both can be calculated in $O(V+E)$ time : $a$ with a simple BFS from $1$, and $b$ by a bottom-up approach of examining the vertices in the reverse topological order.
Now, you consider each edge of the graph $ u \rightarrow v$ and add $w(u,v)$  to the answer iff $a[u]=1$ and $b[v]=1$.
Because the graph is a DAG the two paths above must be disjoint thus their concatenation is a valid path from $1$ to $i$ and since we consider each edge once, there are no duplicates.


Drawing a DFA for a language/regular expression

So, first, your regular expression

$$a^* c^* (aba)^* a^* c^*$$

is not correct. We need to give it the capacity to deal with many $aba$s, any of which can be surrounded by $a$s and $c$s. So, that would give us

$$(a^* c^* (aba)^* a^* c^*)^*$$

Of course, we still have a few more problems. First, we might have no $b$s, which could still fit into the language you've specified. We can fix that by pulling out the first set from our larger expression:

$$a^* c^* ((aba)^* a^* c^*)^*$$

We can't know the order of the $a$s and $c$s, so we need to use the union operator, which behaves essentially like an or in regexes:

$$(a\cup c)^* ((aba)^* (a\cup c)^*)^*$$

We're not done yet, as Thumbnail pointed out, we still need to allow $ababa$, so this gives us Thumbnail's structure, which allows any number of $baa^*$s after an $a$.

$$(a \cup c \cup a (b a a^*)^*)^*$$

Now, as for your DFA, begin with a start state, and let it accept the empty string:

Clearly, we can have as many $c$s as we want without changing our accept state:

$b$s are a little different, because they may be the start of an $aba$ pattern.  This means that we need a new state to encode that we've encountered n $a$:

Now, if we arrive at a $c$, then our $a$ was not the start of an $aba$, and we can return home.  If we get another $a$, then we may still be at the start of an $aba$ set:

Finally, we might exit with a $b$, followed by an $a$, which could be the beginning of a new set:

At this point, we are done.  What we did not put in were the transitions to the garbage state, which are implicitly anything that wasn't yet defined.  If we were to put them all in, we would have a graph that looks more like this:

Notice that one we get to state $g$, there is no way out, and no way to reach an accept state.


Are the algorithms for picking between 2 numbers randomly a lot less computer intensive than the algorithms for picking almost any number randomly?

In principle yes, but in practice probably not; both of them are likely to be extremely fast.
You can randomly choose between two numbers by generating a random bit.  That is extremely fast in practice.
You can't "pick almost any number randomly".  Instead, all you can do is sample from a distribution. The time it takes to sample from a distribution depends on the specific distribution you have in mind.  However, for most cases commonly encountered, this too is very fast.  For instance, if you want to pick uniformly at random an integer from a particular range, that can be done in a standard way by generating some random bits and then using them to select an integer; it will be very fast in practice.
So, while picking between two numbers might be quicker, both operations are likely to be so fast that it's not clear it is worth worrying too much about which is faster.
If you want to understand why this is the case, I suggest you study algorithms for picking a random number and for sampling from various distributions; that will give you a concrete understanding.


How many algorithms solve the same problem?

As far as I can see, there are always infinitely many ways of doing something, even if you try to define and disallow redundant steps.  Let's take the example of sorting.  Even if you restrict to the operations of comparing and swapping numbers, there are infinitely many ways of sorting a list: quicksort the list; swap the first two numbers and then quicksort; swap the first two numbers twice and then quicksort; ...; swap the first two numbers $n$ times, then quicksort; ...

OK, so you try to disallow that as "wasting time". But then there are still infinitely many ways: quicksort; mergesort if the list has length two, otherwise quicksort; mergesort if the list has length three, otherwise quicksort; ...

OK, so you try to disallow that on grounds that quicksort and mergesort will always produce the same answer so the test on the length of the list is redundant. But this is too coarse a notion of equivalence, since now there's exactly one algorithm for every problem – every correct sorting algorithm produces the same answer by definition.


Is there any interesting consequence of $\mathrm{DLogTime}$-uniform ${\mathrm{Mod}_6}^0=\mathrm{NP}$

Even a weaker claim that $\mathrm{DLogTime}$-$\mathrm{uniform}\:\mathrm{AC_2^0}=\mathrm{L}$ readily implies $\mathrm{NP}= \mathrm{PSPACE}$

First, $\mathrm{NP} = \mathrm{EXP}$-$\mathrm{AC_2^0}$ by using a similar argument in this answer. Here, I mean constant-depth $\mathrm{AC}^0$ circuit of depth at most $2$. And, $\mathrm{PSPACE} = \mathrm{EXP}$-$\mathrm{L}$, if you are willing to abuse the notation.

Second, since the mentioned above answer does not describe in details the uniformity of the first-order reduction. I move on to prove the $\mathrm{\mathrm{DLogTime}}$-$\mathrm{uniformity}$ of the standard Cook proof.

That is we need to establish a $\mathrm{DLogTime}$ constructor that constructs a constant-depth circuit, for each input length. And the constructed constant-depth circuits then receives arbitrary input (of given length) and always output correctly.

Indeed, Cook proves completeness of $\mathrm{SAT}$ by using a big tableau.

From the second row of the tableau on, every cell can be computed by a constant-size formula of "nearby" cells of previous row. So, these can be printed as constant output node of the constructed constant-depth circuit. This can be called hard-coded. So, almost all of the constructed constant-depth circuit are merely constant output nodes.

We only need to deal with the first row. This part of the constructed circuit needs to take the actual input bits as its own designated input gates. So, it requires some more indexing work of the constructor. It is worthy mentioning that these actual input bits does not contribute to the variable of the formula output by our constructed circuit (the circuit is a constant-depth reduction, not a decider). This very first part of the constructed circuit can be constructed by the $\mathrm{DLogTime}$ constructor easily. What really makes it into variables of the formulae that will be reduced to by our constructed circuit are the nondeterministic guess bits (also called the witness if you prefer the verifier-style definition of $\mathrm{NP}$). This witness part can also be printed out as constant output gates of the constructed circuit.

Back to your question, we can easily adapt the above argument to deduce that the strange consequence of $\mathrm{DLogTime}$-$\mathrm{uniform}$ $\mathrm{Mod}_6^0 = \mathrm{NP}$ is that $\mathrm{Mod}_6PH = NEXP$. If someone can prove that $\mathrm{Mod}_6P$ is low for itself like $\oplus P$ then the consequence can be strengthened to $\mathrm{Mod}_6P = NEXP$


How can I create 10-character, unique codes with no collisions, but without being predictable?

$36^{10}$ is approximately 52-bit. Now;

Generate a secret key $k$ for AES-128
Encrypt the rowID with $\text{unique_code} = \operatorname{AES}_k(rowID)$, and assuming that the key never changes.

Since AES with a key selects permutation for all possible permutations from $2^{\ell}$ to $2^{\ell}$, where $\ell$ with a key, then by fixing a key, you fixed a secret permutation. Therefore the output is distinct for every distinct input. It is unpredictable since AES is assumed to be secure against Known-Plaintext Attacks.


How to decide if two conjunctive queries cannot have any result in common

Your example queries are not conjunctive queries in the sense I came to know them. On Wikipedia they also are defined differently. What you maybe are looking for is the boolean query evaluation problem. $Q_1(D) \cap Q_2(D)$ can be expressed as $(Q_1 \wedge Q_2)(D)$, thus deciding whether $Q_1(D) \cap Q_2(D)$ is empty is the same as deciding whether $(Q_1 \wedge Q_2)(D)$ has any solution at all.
For conjunctive queries (as defined by Wikipedia) there are algorithms, faster than the brute force method, for this problem, if the query has a certain form, for example acyclic conjunctive queries.


When asking for a lower bound, you should let us know what computation model you're interested in. A good first model to prove lower bounds on is the comparison model. In this case, usually you use the fact that given $n$ values $x_1,\ldots,x_n$, determining whether all of them are unique takes $\Omega(n\log n)$ comparisons. This problem is known as element distinctness or element uniqueness.

In your case, the natural candidate reduction is to map $x_i$ to $(x_i,-x_i)$. Note that no pair dominates each other, but if $x_i = x_j$ then $(x_i,-x_i)$ "weakly dominates" $(x_j,-x_j)$. Therefore any algorithm outputting the number of "weak maxima" can be used to decide element uniqueness, and so requires $\Omega(n\log n)$ comparisons.

You are interested in maxima rather than weak maxima, so you need to tweak this idea a bit. Suppose that all $x_i$ were integers. Then you map $x_i$ to $p_i = (x_i+i/(2n),-x_i+i/(2n))$. Now $p_i$ dominates $p_j$ iff $x_i = x_j$ and $i > j$. So the number of maxima again allows you to decide element uniqueness.

While you can't really assume that the $x_i$ are integers in the comparison model, you can tweak the reduction even further to implement the same effect: you map $x_i$ to $p_i = ((x_i,i),(-x_i,i))$, and you compare pairs of the form $(x,i)$ according to the following rule: $(x,i) > (y,j)$ if $x > y$ or $x=y$ and $i > j$. Every algorithm for computing the number of maximas in the comparison model using $m$ comparisons can be converted to an algorithm for deciding element uniqueness using $O(m)$ comparisons, hence requires $\Omega(n\log n)$ comparisons.


If I understand the problem correctly, there is no polynomial-time algorithm that finds an optimal solution to your problem unless $\mathsf{P}=\mathsf{NP}$.
This holds even in the special case in which all distances are $1$, all populations are $1$, and $x=1$.

To see this notice that, given a graph $G=(V,E)$ and a non-negative integer $n \le |V|$, $G$ admits a dominating set of size at most $n$ if and only if there is a set $S \subseteq G$ with $|S| = n$ such that $\sum_{u \in V : d(u, S) \le 1} 1 = |V|$.

On the bright side, a simple greedy algorithm has an approximation ratio of $\frac{e}{e-1} < 1.582$: iteratively add to $S$ the district $v$ that maximizes the population that falls within distance $x$ of $S \cup \{ v \}$, i.e., the quantity $\sum_{u \in V : d(u, S \cup \{v\}) \ge x} p(u)$.

The approximation ratio of the above algorithm follows from the fact that you can cast your problem as a weighted maximum coverage problem.
In this problem you have a set $X$ of elements and a collection $\mathcal{S}$ of subsets of $X$.  Each element $v \in X$ has a non-negative weight $w(v)$. You are given an integer $k \le |S|$ and you want to select a subset $S$ of at most $k$ sets of $\mathcal{S}$ such that $\sum_{x \in \bigcup_{S' \in S} S' } w(x)$ is maximized.
To reduce your problem to weighted maximum coverage problem pick $X=V$, $\mathcal{S} = \{S_v \mid v \in V\}$ where $S_v = \{u \in V \mid d(u,v) \le x\}$, $w(v) = p(v)$, and $k=n$

Since you can also reduce any instance of weighted maximum coverage problem to your problem, this is essentially the best polynomial-time approximation algorithm that you can hope for. The reduction is as follows: Create a complete bipartite graph $G = (V,E)$ with $V = \mathcal{S} \cup X$ and $E = \mathcal{S} \times X$. Each edge in $E$ has weight $1$. The population $p(v)$ of a vertex $v \in V$ is $p(v) = 0$ if $v \in \mathcal{S}$, and $p(v) = w(v)$ if $v \in X$. Pick $n=k$ and $x=1$.
You can easily see that you can restrict yourself to a solution $S$ that does not select any district in $v \in X$ (since $S \setminus X$ is as good as $S$ and $|\mathcal{S}| \ge k = n$). Then, selecting a subset $S \subseteq \mathcal{S}$ of districts corresponds to covering all the elements in $\bigcup_{S' \in S} S' \subseteq X$, and the population within distance $x$ of a vertex in $S$ is exactly $\sum_{x \in \bigcup_{S' \in S} S'} p(x) =  \sum_{x \in \bigcup_{S' \in S} S'} w(x)$.


NP-completeness of testing whether a SAT formula does not contain any redundant clause

The proof in theorem 1 in [Liberatore'02] shows that irredundancy is NP-hard by reducing SAT to it. Considering any set of non-tautological clauses $\Gamma=\{\gamma_1,\dots,\gamma_m\}$ (think of this as the set of clauses of a CNF boolean formula), it builds in polytime a set of clauses $\Pi_\Gamma$ which is irrendundant iff $\Gamma$ is satisfiable (again, $\Gamma$ being satisfiable means the CNF formula $\bigwedge_{j=1}^m \gamma_1$ is). Therefore if you can solve irredundancy you can solve SAT.
[Liberatore'02]: Paolo Liberatore. 2002. The complexity of checking redundancy of CNF propositional formulae. In Proceedings of the 15th European Conference on Artificial Intelligence (ECAI'02). IOS Press, NLD, 262–266.


Comparing asymptotics of various functions

For the first and the third, taking the logarithm of both sides will really help. For the second, try to use the fact that if $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$ then $f(n) = o(g(n))$. For the fourth, try approximating the sum using an integral.


Are all minimum spanning trees optimized for fairness?

is it possible to have two MSTs in a graph (equal global sum of their edges) but have one of those MSTs contain an edge of higher value than any edge on the other MST in the graph.

No, it isn't; assume it is, let $X$ be the MST with the heavy edge, and call that heavy edge $e := \{u,v\}$. Now there is some other MST $Y$ that doesn't contain edges that are at least as heavy as $e$. In $Y$, we know that there is a path from $u$ to $v$ since $X$ has such a path, so $Y$ must have one as well. Let $p$ denote that path in $Y$. There must be an edge $f$ on $p$ that isn't in $X$, since otherwise $X$ would contain the cycle formed by $p$ and $e$. Now add $f$ to $X$ and delete $e$ from it to get $X'$, which is a spanning tree as well. However, $X'$ has lower weight than $X$ since $f$ has lower weight than $e$, contradicting the assumption that $X$ is an MST.

For something more general which might answer your question more succinctly, here and here are proofs that all MSTs of a graph have the same multiset of edge weights, that is: if $k$ edges of weight $w$ occur in some MST, then $k$ edges of weight $w$ occur in all MSTs for any $w$ and $k$.

Something else that isn't proven in those answers that might be of interest to you: every MST only contains paths with smallest maximum weights for all pairs of vertices $\{u,v\}$, or in words: let $p$ be the unique path between $u$ and $v$ in a given MST $T$ of graph $G$; then for any $u$-$v$-path $q$ in $G$, the heaviest edge on $q$ is at least as heavy as the heaviest edge on $p$.

To prove this, assume that there is some pair $\{u,v\}$ such that the heaviest edge in the unique $u$-$v$-path $p$ in some MST $T$ is heavier than the heaviest edge in some other $u$-$v$-path $q$ in $G$. Let $e$ denote the heaviest edge in $p$; now remove $e$ from $T$, which partitions $T$ into two connected components $U$ and $V$ such that $u \in U$ and $v \in V$. We know that $q$ starts in $U$ and ends in $V$, so there must be an edge $f$ that belongs to the cut $(U,V)$. Now we find that $(T \cup \{f\}) - \{e\}$ is a spanning tree again, and since the weight of $f$ is smaller than the weight of $e$ by assumption, we find that $(T \cup \{f\}) - \{e\}$ has lower weight than the MST $T$, contradicting the minimality of $T$. Thus, no such path $q$ can exist in $G$.

Spanning trees with the heaviest weight being minimal are called minimum bottleneck spanning trees, and you can use the above to show that every MST is an MBST (the converse does not hold, i.e. there may be an MBST that is not an MST, specifically: an MBST might use too many heaviest edges). If an MST $T$ wasn't also an MBST, then there would be a heavier edge in $T$ than in some other spanning tree, and that edge would be on some path, and then the arguments above apply to that path.


Improve worst case time of depth first search on Euler graphs

If I understand correctly, the only way to have a numerically ordered eulerian path would be having a path looking like 1,2,3..,n,1. All nodes in the path must have degree 2 (since you can only get into the once), except perhaps for nodes with degree 0, that you can instead skip.

If this is the case, the algorithm would just be a matter of testing if the 1,2,3..n path is eulerian, with no need to find eulerian paths with a traditional algorithm.


Simple Recognition Algorithm, How Does It Work?

Normally we build a classifier that accepts images of a fixed size: say, 100x100 pixels.  Given an image that is larger than that, we re-scale it to 100x100 pixels before feeding it into the classifier.

This is often combined with other techniques to locate where in a larger image the object is located.  For instance, if you want to detect the presence of a bus in a picture, you build a classifier that recognizes a picture of a bus (where the bus fills the frame).  Then, given a picture that might contain a bus and other stuff, you try cropping out different rectangles from within the image and feeding each one to the classifier.  There are other more sophisticated techniques as well based on deep neural networks and regression.

To learn more, I suggest you read about object detection and object recognition.  There's lots written about the subject in the research literature, and there are excellent tutorials available online.  The state-of-the-art methods use deep neural networks.


Practical applications of Weighted Independent Set in path graph?

I don't think that the weighted independent set problem in paths has many applications.  However, as you point out yourself, it is a very good introduction to dynamic programming and to algorithmic graph theory;  This is one of very many problems that are NP-complete on general graphs but become simpler (or indeed trivial) on restricted input instances.

When you know, and understand, the algorithm for (weighted) independent set in paths, it is not too hard to generalize this to (weighted) independent set in trees and even to graphs of bounded pathwidth and treewidth.

I think that this problem on paths (maybe even on trees, but here I'd love to be corrected) is purely educational.  Indeed, I have hard times finding reasonable applications to Independent Set as well as Vertex Cover, Clique and Dominating Set.


By definition, $A \backslash B$ is the set of all strings $x$ such that $ax \in B$ for some $a \in A$. In our case, $1 \in A \backslash B$ since $01 \in B$ and $0 \in A$, and $01 \in A \backslash B$ since $001 \in B$ and $0 \in A$.


Proof that L^2 is regular => L is regular

Your claim is false. Indeed, it is equivalent to prove that if a language $L$ is not regular, then also $L^2$ is not regular, but this is not true. Here Yuval Filmus gives (possibly) two examples of a non regular language whose "square" is regular, namely $L  = \{ 1^p \mid p \text{ is an odd prime}\}$, under the Goldbach conjecture, and $L'  = \{ 1^{a^2} \mid a \geq 0 \}^2=\{1^n \mid n \text{ is the sum of two squares}\}$.

For a simpler example, consider the set
$$\text{NP}=\{1^n\mid n \text{ is not prime}\}$$
Clearly NP is not regular (otherwise also its complementary would be regular), but NP$^2$ is regular, as its complementary is finite. Indeed, if $n$ is even and greater than or equal to 8, then $n=4+(n-4)$ and $4$ and $n-4$ are not prime and so $1^n\in \text{NP}^2$. Instead, if $n$ is odd and greater than or equal to 13, then $n=9+(n-9)$ and $9$ and $n-9$ are not prime, as $n-9$ is even and greater than 2, and again $1^n\in \text{NP}^2$ (actually, NP$^2=\{1^n\mid n\neq 3\}$, here I don't consider 1 as a prime number).

In general, if $L$ is a non regular language sufficiently "sparse", then there is a good chance that $(L^C)(L^C)$ is cofinite, and then regular. For example, again on a unary alphabet, one can consider the non regular language
$$\text{L}=\{1^n\mid n \text{ is not a power of }2\},$$
then it is easy to see that $L^2=\{1^n\mid n\not\in\{1,2 \}\}$, which is regular.
On a two letter alphabet one can consider the example below of Bernardo Subercaseaux (I think there's a little misunderstanding in his comment, as here we are considering the concatenation of a non regular language with itself), namely the language $L$ that is the complement of the language of well parenthesized strings on the alphabet $\{(,)\}$: in this case $L^2=\{(,)\}^*\setminus\{\varepsilon,(,)\}$, again regular.
Another simple example is given by the non regular language
$$\text{L}=\{w\in\{a,b\}^*\mid w \text{ is not of the form }a^nb^n\text{ with }n>0\},$$
then it is easy to see that $L^2=\{a,b\}^*$: indeed if $w\in L$, then $w=w\varepsilon\in L^2$, else if $w=a^nb^n$ then $w=a\cdot a^{n-1}b^n\in L^2$.


Ideas on how to approach the construction of a probability-heavy algorithm

One plausible approach would be to use integer linear programming.  The following won't be optimal, but it might be decent.

We could try to find quantities $x_1,x_2,\dots$ for the containers, so that if we buy that many containers, the expected number of each item is at least the desired quantity.  This leads to an integer linear program, with one inequality per item

$$\sum_i x_i q_{i,j} p'_{i,j} \ge Q_j$$

where $q_{i,j}$ is the number of item $j$ in container $i$, and $p'_{i,j}$ is the corresponding probability.  Then, we want to minimize $\sum_i x_i p_i$, the total price of these containers, where $p_i$ is the price of the $i$th container.  You could use an off-the-shelf ILP solver to solve for the $x_i$'s, or as a heuristic, use a linear programming solver and ignore that the $x_i$'s need to be integers.

Then, you could randomly sample a container, with container $i$ sampled with weight proportional to $x_i$.  This is a heuristic, but it might help identify which container you most want to buy, so it might work well enough in practice.

You shouldn't expect any efficient algorithm that gives the optimal solution; this problem is NP-hard, by reduction from the knapsack problem.


Show that $f(n) = O(g(n))$ or $f(n) = \overset{\infty}{\Omega}(g(n))$

If you consider the following functions defined for $x\in \mathbb{R}$:
$f(x) = \left\{\begin{array}{rl}1 & \text{if }x\in\mathbb{N}\\x&\text{otherwise}\end{array}\right.$ and $g(x) = \left\{\begin{array}{rl}x & \text{if }x\in\mathbb{N}\\1&\text{otherwise}\end{array}\right.$
Then you have:

neither $f \in O(g)$, because whatever the constant $C$, $x\in]C,+\infty[\setminus \mathbb{N}\Rightarrow f(x)  > Cg(x)$;
nor $f\in \overset{\infty}{\Omega}(g)$ because whatever the constant $C$, $n\in]\frac{1}{C},+\infty[\cap\mathbb{N}\Rightarrow f(n)<Cg(n)$ (so there cannot be infinitely many integers so that $f(x) \geq Cg(n)$).

So the question here implicitly supposes that the big Oh notation considers that $n\in\mathbb{N}$ (and I think that's why the chosen notation is $n$).


It suffices to show that Quicksort runs in time $f(n) = O(n^2)$ in the worst case, since this immediately implies that it also runs in at most $f(n)$ time on average.
The recurrence equation that describes the worst-case running time for Quicksort is
$$
T(n) = T(n-1) + \Theta(n),
$$
which has solution $T(n) = \Theta(n^2)$.


how one memory can be accessed simultaneously in instruction fetch and data read?

Modern CPUs usually feature separate instruction and data caches, so effectively, even if from a software PoV, everything is coming from a single memory space, there are physically separate busses and memories for instructions and data ("harvard", which is used for all reasonably fast CPUs nowadays).

There are also multi-port memories able to sustain several accesses simultanously. There is a great variety of architectures, for example DSPs or GPUs may have different memory organization than traditional CPUs.

In computers, with something like an x86 or an ARM, with an OS and applications, code memory is separate from data memory (there are attributes in MMU mappings), code is read-only. Except during on-the-fly dynamic compilation, or some library linkage, code is never modified through data accesses, there is no self-modifying code. It is nowadays far more efficient to have separate code and data memories for first level caches.

Many years ago, when one couldn't put billions of transistors on a die, there were shared or off-chip caches, and sometimes data accesses could effectively stall instruction fetches.


Closure of regular languages under non-contiguous subsequence

Here are several ways of showing this:

Starting with a DFA/NFA for $L$, add $\epsilon$ transitions parallel to all other transitions.
Apply the regular substitution that maps $\sigma \in \Sigma$ to $\{\sigma,\epsilon\}$.
Starting with a regular expression for $L$, replace all copies of each $\sigma \in \Sigma^*$ by $\epsilon + \sigma$.


Generate Evenly Distributed Pattern Based on Weights

Normalize $W$ by calculating the greatest common divisor of $W$ and dividing every element by it.

Then just repeatedly iterate over $W$ in order, and if $W_i > 0$ subtract $1$ from it and output $A_i$. You stop when all $W_i = 0$.

If $1, 2, 2, 3, 3, 1, 2, 2, 3, 3, \dots $ in your example is also fine then just output $W_i$ copies of $A_i$ after normalization.


How to calculate the miss ratio of a cache

Yes. The hit ratio is the fraction of accesses which are a hit. The miss ratio is the fraction of accesses which are a miss. It holds that
$$ \text{miss rate} = 1-\text{hit rate}.$$

The (hit/miss) latency (AKA access time) is the time it takes to fetch the data in case of a hit/miss.
If the access was a hit - this time is rather short because the data is already in the cache. But if it was a miss - that time is much linger as the (slow) L3 memory needs to be accessed.
The latency depends on the specification of your machine: the speed of the cache, the speed of the slow memory, etc.


Steiner tree problem with the known optimal subset of Steiner vertices in approximation algorithms

It can be proved as I mentioned with  contradiction, assume that $S1$ is the optimal subset of steiner nodes and $R$ is the required nodes, so we give the subgraph of main graph including $S1$ and $R$ nodes and the edges between them to Kroskal algorithm then we have a MST for them, we assume that it is not equal to OPT (solution for steiner tree problem), so the given subset (S1) was not optimal I mean at least one steiner node was not given or was given falsly.


How to compare n number of m-dimensional points among one another with minimum time complexity?

So you suggested the basic technique of checking all pairs which is $O(mn^2)$. Here are some things you can try first, at lower complexity, before falling back to an approach with a similar worst-case bound but likely better constants.

We represent each point $p_i = (x^i_1, \dots, x^i_m)$.

Then clearly there is a dominated pair if $\min_i \max_j x^i_j \leq \max_i \min_j x^i_j$. The time to evaluate this is $O(mn)$.

Next, we sort the points $m$ times, by each dimension. Let $r^i_j$ and $R^i_j$ be the indexes at which $p_i$ appears in each list (in range $[0,n)$), where the $r$ values have tie-breaks resolved down and $R$ values have tie-breaks resolved up, respectively. In other words, considering the values $3, 5, 5, 6$. Then the $r$ and $R$ values for the two points having $5$ would be $1$ and $2$. The time to evaluate this is $O(mn \log n)$, before we check conditions.

If $\min_i \max_j R^i_j \leq \max_i \min_j r^i_j$, then there is a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Next, let $w_i = \sum_j r^i_j$ and $W_i = m(n-1) - \sum R^i_j$. Note that $w_i$ is an upper bound on the number of points that can't dominate $p_i$. Similarly, $W_i$ is an upper bound on the number of points that $p_i$ can't dominate. Thus, if $\min_i w_i < n - 1$ or $\min_i W_i < n - 1$, then there must be a dominated pair. The additional time to evaluate this is $O(mn)$ leaving the total time as $O(mn \log n)$.

Finally, as a fallback, for each point $p_i$ we know there are at most $\min_j R^i_j$ points which $p_i$ can dominate. Thus, knowing which list each $p_i$ obtained its minimum $R^i_j$ can give us a shorter list of points to check. The time here is still $O(mn^2)$ in the worst case, but the constant will be better than all pairs.


To count all perfect matchings containing an edge $e = (x,y)$, simply remove both endpoints $x,y$. To count all perfect matching not containing the edge $e$, simply remove the edge.


Number of states in NFA and DFA accepting strings from length 0 to n with alphabet Σ= {0,1}

You can define DFAs in both ways. One can require the transition function to be total, but it is indeed fine to define DFAs without this requirement. You (or your lecturer) just choose one definition and stick with it.


Let $f(n) = n^2\log n$, with the $\log$ taken to base 2. Then
$$
\frac{f(2n)}{f(n)} = 4 \frac{\log(2n)}{\log n} = 4 \left(1 + \frac{1}{\log n}\right).
$$
That is, for large $n$ you would expect $f(2n) \approx 4f(n)$. This shows that this test isn't sensitive enough to detect logarithmic factors.


$\{a,b\}$ is set notation. The alphabet of a language is the set of all possible symbol used in the language. You can substitute the typical $\Sigma$ for the full set every time.

$\Sigma^*$ (where $^*$ is the kleene star) is the set of all possible strings you can make with that alphabet. That includes strings that happen to not use a certain character.

Therefor $\{w \in \{a,b\}^* : w \text{ contains } bbb\}$ is equivalent to $\{w \in \Sigma^* : \Sigma =  \{a,b\} \text{ and } w \text{ contains } bbb\}$. But it skipped defining $\Sigma$ for terseness reasons.


Assertion of Type Inference Rules/Type Checking

Well, you need to construct a typing derivation which has what you want to prove as a conclusion, and no open premise (i.e., leaves must be axioms, or rules with no premises). In the case of your example, the conclusion will be

$$ int\;x,\,int\;y\;\vdash\;(x < (x \times y) + x) : bool $$

so the proof will start by

$$ {int\;x,\,int\;y\;\vdash\;x : int \quad\quad\quad
  int\;x,\,int\;y\;\vdash\;((x \times y) + x) : int}
  \over {int\;x,\,int\;y\;\vdash\;(x < ((x \times y) + x)) : bool} $$

and then you continue building up the tree until you reach leaves (i.e., rules with no premises). This will immediately be the case in the left branch since you only have a variable.

Here is the full proof (as an image):


Problems for which a small change in the statement causes a big change in time complexity

Given a graph, does it have a cycle of length $3$ ($4$)? Four-cycles there is an easy algorithm that requires $O(n^2)$ time. The best known algorithm for triangle detection is related to matrix multiplication and has complexity $O(n^\omega)$ where $\omega$ is the matrix multiplication exponent. It is an open problem to determine whether $\omega=2$.
Given a graph, decide if its vertices can be colored with 2 (3) colors. Two colors: it is equivalent to testing the graph for bipartiteness, Three colors: NP-Complete.
Given a graph, decide if its edges be colored with 2 (3) colors.
Two colors: trivial (color an first edge arbitrarily, follow all implied edges, repeat). Three colors: NP-Complete.
Given a system of Diophantine equations, does it a admit a (non-negative) solution? Solvable in polynomial time if variables can be negative, NP-Complete otherwise.
Given a graph and two vertices $s$ and $t$, what is the length of the shortest (longest) path between $s$ and $t$? Shortest path: essentially a BFS. Longest path: NP-hard.
A lot of graph problems that are hard in general, are easy on trees (vertex cover, independent set, dominating set, ...). See Kleinberg & Tardos, perfect graphs, and notice that a minimum dominating set on a tree can be found by greedily selecting a parent $v$ of a leaf, deleting $v$ and its neighbors, and repeating.
Given a directed graph, can you partition its edges into paths of length 2 (1)? For paths of length 1 the problem is trivial. For length 2 there it is a generalization of 3-dimensional-matching.
Given a set of numbers, can it be partitioned into groups of 2 (3) elements so that all groups have the same sum? For groups of two elements it is trivial (the match of an element is completely determined by the element itself). For groups of $3$ it is the 3-partition problem.
Given a NFA, does it accept (reject) at least one word? Accept: this boils down to a connectivity check between the initial state and the final states. Reject: PSPACE-Complete (search Universality problem).
Given a graph $G$, two vertices $s$ and $t$, and $c \in \mathbb{N}$. Does $G$ contain $4$ ($5$) edge disjoint paths of length at most $c$? For 4 paths the problem is solvable in polynomial time, for 5 paths it is NP-hard.
Given an edge-weighted graph $G$ and two vertices $s$ and $t$, what is the minimum (maximum) weight of a $s$-$t$ cut in $G$? See minimum-cut (polynomial) and maximum-cut (NP-hard).
Given a set of linear constraints, is there at least one (integral) point in their intersection? Solvable in polynomial-time if variables are not restricted to be integers, otherwise NP-hard.


Terms and definitions for regular language and NFA

Let $L$ be a regular language. There exists a NFA for $L$ in which $\delta(q,\sigma)=\varnothing$ (for every final state $q$ and every symbol $\sigma$) if $\lambda\notin L$.

We can make this into a characterization: iff $\lambda\notin L$ or $L = \{ \lambda\}$.


Does this excerpt from the linear probing Wikipedia page make an assumption?

Yes, it is assumed that probing sequences are identical during the search and insertion. In theory you could use a different probing sequence (e. g. check h(x) index first, then h(x) + 2, and only then h(x) + 1), but it doesn't make any sense - you are better off always using the same sequence to have the minimal expected number of probes.


There is probably a proof in Karp's original paper. Here is a simple reduction from SAT. Given an instance $\varphi$ of SAT with $m$ clauses, construct an instance of MAX-CLIQUE as follows. For each clause $C$ and each literal $\ell$ appearing in $C$, there is a vertex $(C,\ell)$. Two vertices $(C_1,\ell_1),(C_2,\ell_2)$ are connected if $C_1 \neq C_2$ and $\ell_1 \neq \lnot \ell_2$. This has a clique of size $m$ iff $\varphi$ is satisfiable (exercise).


Master Theorem and rounding up to the nearest integer

Yes, this is generally valid.  Normally, you can just replace $\lceil n/b \rceil$ with $n/b$ and carry on.

Why is this valid?  Let me give three explanations, in order of decreasing amount of hand-waving:

Informally, it probably won't make much difference, and probably not enough to change the asymptotics.  Asymptotic analysis is about what happens when $n$ gets really big, and when $n$ is really big, there's very little difference between $\lceil n/b \rceil$ and $n/b$ (rounding effects become negligible).
Slightly less informally, this is OK when $T(n)$ is a monotonically increasing function of $n$. To justify this, we can start by focusing only on the case where $n$ is a power of $b$, i.e., $n=b^k$.  Then the ceilings can be ignored (they do nothing), and the master theorem will apply for sure to $n$ of that form.

So, the standard proof of the master theorem will show that $T(n) \le f(n)$ when $n$ is a power of $b$.  What about other values of $n$ that aren't a power of $b$?  Well, if $n$ isn't a power of $b$, just round up to the nearest power of $b$: $T(n) \le T(b^k)$ where $k = \lceil \lg_b n \rceil$.  Since $f(n)$ grows at most polynomially, it can't grow too fast, and we'll have some constant $c$ such that $f(b^k) \le c \cdot f(b^{k-1})$.  Then we know that $T(n)$ is bounded within a narrow range:

$$f(b^{k-1}) \le T(n) \le c \cdot f(b^{k-1}).$$

The upper and lower bounds differ by only a constant factor, so everything gets absorbed into the big-O notation.
A more formal justification can be found at Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem.


This is still a form of pseudocode, obviously just not of the form you might have seen thus far. It is worth noting that there is not strict standard or rules for writing pseudocode, as long as it describes the solution to a problem in such a way that someone could then implement it in a language of their choice.

The term pseudocode simply refers to some notation resembling a programming language, aimed more towards human readability and understanding rather than some language-specific syntax.


Hennessy and Patterson (Computer Architecture: A Quantitative Approach) use the term "multithreading" to refer to running more than one thread on a single core.

Their distinction between "fine-grain", "coarse-grain" and "simultaneous" involves different approaches for how the threads share the issue logic (the logic that moves instructions from the decode pipeline stage to the execute pipeline stage.)

In "coarse-grain multithreading" the issue stage will issue instructions from one thread for many cycles (dozens or hundreds) and then switch to issuing from another thread only when the first thread gets a cache miss or some other long-latency operation.

In "fine-grain multithreading" the issue stage can issue instructions from a different thread each cycle, but all the instructions issued together in a cycle must come from the same thread.

In "simultaneous multithreading" the issue stage can issue instructions from different threads in the same cycle.  The restriction is lifted that instructions issued together in the same cycle must come from the same thread.  The distinction between fine-grain multithreading and simultaneous multithreading only matters on machines that can simultaneously issue two or more instructions.


What exactly is the difference between a Balanced Binary Search Tree and an AVL tree?

There are some implementations of Balanced Binary Search Trees, also known as Self-balancing Binary Search Trees. One of the aspects that can be considered when balancing a tree is it's subtrees height difference. This height aspect aims to keep the tree as flat as possible. The more flat the tree is, the less levels it will have and the search will be faster.
The implementation that you mentioned reconstructs the entire tree when a new node is inserted, from the root to the leaves. The AVL tree will reorganize (balance) only the subtrees needed to meet its invariant, i.e., the height difference less or equal to one, when a new node is inserted or a existing node is removed.
The pre-order traversal will be different, since these two BBSTs have different implementations! If you test, maybe a red-black tree (another BBST), the preorder will be different too!
The main thing to keep in mind is that the reason of the BBSTs to exist is that they will keep them more flat as possible to speed up the search for nodes. The only traversal that will be equal among them (if they are search trees) is the in-order traversal, that can be also used to sort data.


Minimal Number of Fixed Size Sets to contain all Sets

If the sets are chosen randomly, then for the parameters you chose, the problem can be solved efficiently.  In particular, the following trivial algorithm will output the correct answer with high probability: take each set of $S$, pad it by adding 10 random elements, and output the result (all sets of $S$, padded).

This might sound wasteful, but for the parameters you mentioned, if the sets are chosen randomly, it's unlikely you can do better.  You can only do better if there exist two sets $s,t \in S$ that can be covered by a 25-element set, i.e., such that $|s \cup t| \le 25$.  This happens only if $s,t$ have at least 5 elements in common (i.e., $|s \cap t| \ge 5$).

Now when $s,t$ are chosen uniformly at random from all possible sets of size 15, the probability that they have two elements at random is very small.  It is approximately ${15 \choose 5}^2/1000^5 \approx 9 \times 10^{-9}$.  Also, there are ${1000 \choose 2}^2$ possible pairs $s,t$, so by a union bound, the probability that there exist two such sets $s,t$ is about $0.0045$.  This means there is only a small probability that you can cover two sets from $S$ by a single set of size 25, if the sets of $S$ are chosen randomly.

In general, for your problem, one approach would be to find all pairs of sets $s,t \in S$ that overlap in at least 5 elements.  Build a graph where $S$ is the vertex set and you add an edge between $s,t$ if $|s \cap t| \ge 5$.  Find a maximum matching in this graph.  Then you can use this to build a set of 25-size sets (one 25-size set per edge in the matching, plus one set per vertex not touched by the matching).  However, if the sets are generated randomly, this is unnecessary as it is unlikely  to find any pair of sets that overlap in at least 5 elements.

Anyway, if the sets are chosen uniformly at random, the problem is uninteresting for the parameters you gave.  If the sets aren't chosen uniformly at random and have some structure, I recommend that you edit the question to describe this structure.


As an example, Yellow denotes a target, red cells indicate the radius of the target such that if a bomb was placed in any of the red cells, it would blow up a target.

We can see from the picture that if we listed all the co-ordinates that are red

Pseudocode // Note that this tries to add the centre, or the x,y of the target twice
for target in targets:
    for i in range(-radius, radius):
        set[target].add(target.x + i, target.y)
        set[target].add(target.x, target.y + i)

Then compare two sets for overlap, and if there is overlap between all of them, then we have an answer.

Pinky Purple is a bomb, and the blue is the radius that if another bomb explodes within, it will detonate too

Note that now we have to do a check before adding the co-ordinate to the set

If it is a blank cell it is easy, just add it.

If it is a bomb, dont add it, but add all the possible co-ordinates that will set off the bomb, and if during our checks, we encounter another bomb, we need to add that list too. I would make a recursive method here

def bombLinks(candidate.x, candidate.y, bombSet):
    for i in range(-radius): //0 to the -radius shouldn't be checked for bombs, since thats where we came from
        candidateType = blockAtCell(candidate.x + i, candidate.y)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x + i, candidate.y)
        candidateType = blockAtCell(candidate.x, candidate.y + i)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x, candidate.y + i)

    for j in range(radius):
        candidateType = blockAtCell(candidate.x + j, candidate.y)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x + j, candidate.y)
        else if(candidateType = "Bomb"):
            bombSet.add(bombLinks(candidate.x + j, candidate.y, bombSet))
        candidateType = blockAtCell(candidate.x, candidate.y + j)
        if(candidateType = "Blank"):
            bombSet.add(candidate.x, candidate.y + j)
        else if(candidateType = "Bomb"):
            bombSet.add(bombLinks(candidate.x, candidate.y + j, bombSet))
    return bombSet

If it is anything else, we could ignore it, or if we want it so that explosions can't pass through certain blocks, we can do some more checks here

for target in targets:
    for i in range(-radius, radius):
        candidate.x, candidate.y = target.x + i, target.y
        candidateType = blockAtCell(candidate.x, candidate.y)
        if(candidateType == "Blank"):
            set[target].add(candidate.x, candidate.y)
        else if(candidateType == "Bomb):
            set[target].add(bombLinks(candidate.x, candidate.y, []))

        candidate.x, candidate.y = target.x, target.y + i
        candidateType = blockAtCell(candidate.x, candidate.y)
        if(candidateType == "Blank"):
            set[target].add(candidate.x, candidate.y)
        else if(candidateType == "Bomb):
            set[target].add(bombLinks(candidate.x, candidate.y, []))

Whew, thats a lot of code, and you may have a better way of traversing the list of possible bomb locations, just don't forget that you can end up in an infinite loop if you check for bombs both directions

After all that, check the overlap between the sets. If there is an answer, great, otherwise pick the location that came up the most

Please excuse my terrible pseudo code, especially the loops


Can sampling remove the limitations in greedy algorithm?

It's unclear why you single out the greedy algorithm; there are many different algorithms for combinatorial optimization, the greedy algorithm (or rather, greedy-like algorithms, also known as myopic algorithms) being only one of them. That said, I have a positive answer and a negative answer for you.

Positive answer. Consider the problem of maximizing a non-negative submodular function under a cardinality constraint. In this problem, you are given a submodular function $f$ over a domain $U$, and a bound $k$. Your task is to find a subset $S \subset U$ of size at most $k$ such that $f(S)$ is as large as possible. This problem is hard (more on that below), and so we make do with approximation algorithms. The greedy algorithm has no guarantees in this regard, but a simple modification of it gives a (probably non-optimal) $1/e$ guarantee. See Buchbinder–Feldman–Naor–Schwartz.

Negative answer. In what sense is the problem of maximizing a non-negative submodular function under a cardinality constraint hard? One such sense is hardness in the value oracle model. Suppose that an approximation algorithm is given oracle access to the function $f$. Then if $f$ always produces a $1/2+\epsilon$ approximation, there must be some $f$ and $k$ for which it calls the oracle exponentially many times (in $n = |U|$), a result due to Vondrák. This hardness result holds even for randomized algorithms (with any constant success probability). So randomization has its limits as an ingredient.

Does randomness help? Take the closely related problem of unconstrained submodular maximization – the case $k = n$ (recall $n = |U|$) of the problem considered above. The algorithm of Buchbinder–Feldman–Naor–Schwartz yields the optimal 1/2 approximation, but is randomized. They also give a 1/3 approximation algorithm which is deterministic, matching previous guarantees of Feige–Mirrokni–Vondrák. Can deterministic algorithms achieve the randomized guarantee? (Rumour has it that the answer is: Yes.)

Can randomization help? Under the widely held belief that P=BPP, there cannot be any discrepancy between randomized and deterministic polytime algorithms. However, this holds only in the model in which the input is given explicitly. In the value oracle model, the input is given implicitly as an oracle, and so it could be that randomized algorithms outperform deterministic ones. Indeed, it is easy to come up with specific tasks which are much easier for randomized algorithms. The question is whether unconstrained submodular maximization is one of these examples.


Is there an efficient algorithm for solving tiling puzzles?

Tiling figures of the plane with two bars shows that this problem is NP-complete in the general case. Simply have the horizontal and vertical bar the same size $\geq 3$.


Recommendation for good book or online course on distributed programming

This is awesome book:
Designing Data-Intensive Applications
https://www.amazon.com/Designing-Data-Intensive-Applications-Reliable-Maintainable/dp/1449373321
You may find the review here:
https://www.goodreads.com/book/show/23463279-designing-data-intensive-applications


Why are those very similar languages in a different complexity class?

It's because the running time to test $k$ DFAs, each of size $n$, is something like $\Theta(n^k)$.  This is polynomial when $k$ is fixed (like 2), but exponential when $k$ is not fixed (e.g., when $k=n$, you get something like $n^n$).

(We don't actually know for sure what the best running time for that is, but we suspect it's something like that; and that will explain why those similar-sounding problems have different complexity classes.  Likewise, we don't actually know for sure that P is a different complexity class from NP, but we suspect it is.)


Intersection and partial quantity decidability

For your first question, the answer is that $X\cap Y$ will not necessarily be decidable. Let $Y$ be an undecidable language over an alphabet $\Sigma$ and let $X=\Sigma^*$. Then obviously $X$ will be decidable and $X\cap Y=Y$ will be undecidable. On the other hand, the intersection may be decidable, as we could show by letting $X=\emptyset$.

For your second question, I assume that by "$Y$ is a partial quantity of $X$" you mean that $Y$ is a subset of $X$ (i.e., $Y\subseteq X$). Then we can do a similar construction, letting $X=\Sigma^*$, and $Y$ be undecidable, so again, $Y$ may or may not be decidable.

It's worth mentioning that this latter result frequently trips up students. Very few properties of languages are closed under subset/superset: there's no guarantee that a subset of a regular language will be regular, for example.


necessary and sufficient pumping lemma - bounded pumping variant

Yes, what you have observed is correct. We can, in fact, always take $N=0$. Here is the variant of Jeffrey Jaffe's pumping lemma where strings are pumped up or down exactly once.

A language $L$ is regular iff $\exists k$, $\forall x\in \Sigma^k$, $\exists u,v,w\in \Sigma^*$ such that $  x=uvw$, $|v|\ge 1$ and $\forall z\in \Sigma^*$,
$$uvwz\in L \iff uwz\in L.$$

As you have observed, the article has basically proved the above fact.

Here is a simpler proof of the "$\Longleftarrow$" direction. Let $[y]$ be the Myhill-Nerode equivalence class represented by string $y$. Suppose $|y|\ge k$.

Let $x$ be the first $k$ symbols of $y$ and $t$ be the rest of $y$, i.e., $y=xt$ and $|x|=k$. By assumption, there exists $u,v,w\in\Sigma^*$ such that $x=uvw$,  $|v|=1$ and
$$yz=x(tz)=uvw(tz)\in L\iff uw(tz)=(uwt)z\in L.$$
The equivalence above means $[y]=[uwt]$. Since $uwt$ is $y$ with $v$ deleted, $|uwt|\lt |y|$. That means the shortest string in a Myhill-Nerode equivalence class must be shorter than $k$.

Since there are finitely many strings that are shorter than $k$ symbols, there are only finitely many Myhill-Nerode equivalence classes. By the celebrated Myhill-Nerode theorem, $L$ is regular.


Set of all countably infinite strings over a finite alphabet >1

Take the alphabet $\Sigma = \{0,1\}$ and consider strings whose positions are indexed by $\mathbb{N}$ (also known as $\omega$-words).  There is a one-to-one correspondence between these strings and subsets of $\mathbb{N}$ given by $x_0x_1x_2\dots \leftrightarrow \{i\in\mathbb{N}\mid x_i=1\}$. Therefore, there are as many $\omega$-words as there are subsets of $\mathbb{N}$, and this is an uncountable number.

This holds for any countably infinite word length.


This is similar to the proof that PP contains NP. Given a 3SAT instance $\varphi$ on $n$ variables, construct a machine $M$ that with probability $3/4 - 2^{-n}/4$ accepts, and with probability $1/4 + 2^{-n}/4$ chooses a random truth assignment and accepts if the truth assignment satisfies $\varphi$. If $\varphi$ has $N$ satisfying assignments, then $M$ accepts with probability
$$
p = \frac{3}{4} - \frac{2^{-n}}{4} + \frac{M}{2^n} \left(\frac{1}{4} + \frac{2^{-n}}{4}\right).
$$
If $M = 0$ then $p < 3/4$, whereas if $M \geq 1$ then $p \geq 3/4 + 2^{-2n}/4$.

I'll let you fill in the rest of the argument.


What is the trick of "adding a huge number" for in the reduction from 3-Partition?

The large $B$ is here to ensure that the squares follow the pattern shown in the figure.

In the part "there exists a packing $\Rightarrow$ there exists a 3-partition". You need to exhibit tripples of integers with sum $=t$. This is easy if the coding squares in the packing are arranged 3-by-3 as in the picture, but how do you know this is the case? For instance, with very slightly smaller blue squares, you could have two small squares side by side in the same column, and then you'd be in trouble.

One way to use the trick of the $B$ constant is to say that it is not possible to have any horizontal line crossing strictly more than $n/3$ squares (such a line has length $(B+t)\frac n3$, a square has size at least $B$, and $B > t\frac n3$). So each horizontal line meets a 1st square, a 2nd square, etc., and then you can show (again using the large $B$), that the $i$th squares of each lines must all meet in the same column. Once you've got this, then you  get a 3-partition.

About Question 2, it is obviously hard to give a formal answer, but the general pattern is the following:with 3-partition, you need to introduce some kind of slackness to allow that any integer in an interval $[min,max]$ can be somehow encoded and embeded in a slot (which must then correspond to the maximum possible size). But then a common issue is having two integers fitting in the same slot, or more generally other overlapping issues (as with the squares here). This is solved by making sure that the $min$ is large enough compared to the slot size (we often need $min > max/2$, or $min > max*(n-1)/(n)$ here): this is easily achieved with an additive constant $B$.

Edit Sample instance where $B$ is necessary:
Let the instance of 3-partition be $(10,7,2,10,9,2)$ with $t=20$. This is a no-instance. However, with $B=0$, you have a valid packing of the $40\times 20$ rectangle: use a first column with four squares $(10,7,2,2)$, the last two being side-by-side, and a second column with only $(10,9)$. This is not possible with, say, $B=100$, and a $240 \times 320$ rectangle.


By definition, all NP-complete problems are decision problems. In fact, the category of NP-completeness only applies to decision problems. Any other kind of problem cannot be NP-complete any more than an apple.

A decision problem A is in NP if there is an integer $m$ and a decision problem B, which can be decided in polynomial time, such that:

If $x \in A$ then there exists $y$ of size at most $m|x|^m$ (here $|x|$ is the size of $x$ in bits) such that $\langle x,y \rangle \in B$.
If $x \notin A$ then for every $y$ of size at most $m|x|^m$ it holds that $\langle x,y \rangle \notin B$.

The string $y$ is called a witness.

This definition is a bit abstract, so let me explain it using your example, the Max Cut problem. The Max Cut problem, as a set, consists of all pairs $\langle G,k \rangle$ such that $G$ is a graph containing a cut which cuts at least $k$ edges. The desired witness $y$ is a cut which cuts at least $k$ edges. The decision problem B consists of all pairs $\langle \langle G,k \rangle, C \rangle$ in which $G$ is a graph and $C$ is a cut in $G$ which cuts at least $k$ edges. The problem Q can be decided in polynomial time – that is, given a graph $G$, a cut $C$ in $G$, and an integer $k$, it is easy to check whether $C$ cuts at least $k$ edges. The size of $C$ is also polynomial in the size of $\langle G,k \rangle$.

As jmite explains in the other answer, this definition is equivalent to the more usual one: NP consists of all decision problems which can be decided using non-deterministic polynomial time machines. Let me sketch why the two definitions are equivalent.

Suppose first that A is in NP according to the definition stated above. The non-deterministic polynomial time machine deciding A guesses the witness $y$ and then verifies it (using the polynomial time algorithm for B), accepting if the verification succeeded.

For the other direction, the sequence of non-deterministic choices functions as the witness $y$. We can verify that a specific sequence leads to acceptance by running the non-deterministic polynomial time machine using $y$ as its choices.


Any modern compiler consists of multiple phases, at least

lexing,
(context-free) parsing and
target code generation.

Additional phases are static analysis (names, types, ...) and optimisations.
Each phase uses the result of the prior as input.

Now, the lexer processes the actual program text and transforms it into a token stream. For instance, the (sub)string "abc" becomes a token StringLiteral("abc"), if becomes IF and myMethod becomes Identifier("myMethod"). Tokens typically hold additional information, e.g. their position in the original program text. The context-free grammar used for syntax parsing is expressed in terms of these tokens, usually ignoring their parameters.

At this point, it should be clear that handling whitespace is nothing crazy: instead of dropping all whitespace (like a Java compiler would do), you could as easily lex the strings "  " or \t to a token Indentation used in the grammar.


Can the Dijkstra algorithm work with a negative arc?

The most common implementation of Dijkstra's algorithm (for example, the one you find on Wikipedia), will not work correctly in this case, because once a node is extracted from the priority queue, its label (distance from the source) will never be revised.  Consider the following example: there are four nodes $a,b,c,d$ (node $a$ is the source), and four arcs: $a \rightarrow b$ with cost 10, $a \rightarrow c$ with cost 4, $b \rightarrow c$ with cost -8, and $c\rightarrow d$ with cost 1. With the classic implementation, Dijkstra's algorithm will extract node $c$ from the queue before node $b$, and hence will report 5 as the length of the shortest path from $a$ to $d$, while the correct answer is 3.

There is, however, a conceptually simple modification that guarantees correctness of the algorithm on any instance with negative weights but no negative cycles. You simply put back a node in the priority queue after you discovered a shorter path to it. In the above example, after the node $b$ is expanded we discover a shorter path to $c$, and put $c$ back in the queue. Expanding $c$ one more time allows to find the correct path to $d$.

Note however that, while correct, the running time of this "revised Dijsktra" is no longer the same as the original implementation, because now we may have to expand the same node multiple times. In fact, the running time can be exponential in the number of nodes.


How different is the working of SNN (Spiking Neural Network) as compared to a real Neuron System in biological systems?

There are different types of spiking neural network models:

Hodgkin-Huxley: models the processes within a neuron with electrical parts. This results in differential equations with 4 variables (capacity of the membrane, resistance of the ion channels, balance potentials, openings of the ion channels).
Leaky integrate and Fire (LIF): Probably the simplest SNN; it is only an ordinary first order differential equation
Spike Response Model: models refraction time. It tries only to model the phenomena. Although it is simple, it is still more accurate than LIF.

I don't have a biology background, but I would say the Hodgkin-Huxley model is probably the closest to real neurons. However, as far as I know (which is very little), there is no (effective, plausible) training algorithm. So this is probably the key difference to the brain. Also the topology will certainly be different.

And, of course, we can model much less spiking neurons than we have natural neurons in a human. So the number of neurons is a key difference, too. I've heard SNNs have a few dozend neurons, probably up to several hundred neurons. The biggest MLP (CNN) models I've seen so far have about 150 000 neurons (see Deep Residual Learning for Image Recognition). The human brain has about 86,000,000,000 neurons (see Wikipedia).


How to identify periodic pattern recognition

One way to detect a pattern is to write a filter that scans the entire sequence and returns true/false at each point.  True means that the pattern was recognized, false means that it was not found.  Count the number of "true" values and divide by the entire length to see the fraction of times that the pattern was found.

For example, one filter would require three parameters: f, the expected frequency (60 seconds); w, the allowed width (2 seconds means 58-62 seconds); and d, the allowable difference between values.

In Python code:

f = 60    # frequency, every 60 points
w = 2     # width, (point - f) +/- w
d = 10    # delta, allowable difference

points = [... list of data points ...]
n = len(points)

found = 0     # start counting the number of matches
# main loop: start at point f+w so we can look back that far
for p1 in range(f+w, n+1):
    # compare point p1 with point p0, looking back (f +/- w)
    for p0 in range(p1-f-w, p1-f+w+1):
        if abs(points[p1] - points[p0]) < d:
            found += 1    # filter found a match
            break         # exit innermost loop
print 100.0 * found / (n - f - w)    # show the percentage of matches

You can play around with the parameters, and maybe use d as a percentage instead of an absolute value.

For more complex pattern recognition, you will need to write more complex filters.  This is a start.


No, you couldn't say that, because it's not true.

A helpful method is to prove all your claims.  Don't just guess -- try to find a proof.  If you're struggling to find a proof, the first thing to check is whether maybe the thing you're trying to prove is false, so look for a counterexample.  In this case you should easily be able to find a counterexample to your claim.  Alternatively, if you can't find a proof and can't find a counterexample, look for a different approach or a different way to solve the problem that uses only facts you do know how to prove correct.


Find an infinite set of strings that are compressable better than in $O(\log n)$ space

Hint:

   Instead of $a_i = b^i$, try $a_i = b^{f(i)}$ for some function $f$.


Why does an admissible heuristic mean A* is optimal?

With an admissible heuristic

The heuristic defines which nodes will be explored first, but does not change the final path found.

In your example, the heuristic will cause the path to Z to be explored first.  The algorithm will discover the true (expensive) cost of 120.  Then it will decide to explore the A path and discover the optimal route.

A better heuristic would guess A was the way to go immediately, find the cost of 100, and never bother exploring Z at all (e.g. if the heuristic said the cost was greater than 100).

So the heuristic changes the execution time, but not the final answer.

With an unadmissable heuristic

If the heuristic marked A as costing 130 (when the true cost is 100), it may find the route to Z (true cost 120), and instantly stop (because it "knows" the cost to A is at least 130), so return the wrong answer.


What is the signal going from the computer to the screen?

The memory you are asking about really exists and is called framebuffer. However, it's not easy to directly access this memory on modern computers, because it's intentionally hidden from user processes.

For more info - click here.


What is the difference between Big O and Theta notation in terms of inputs?

The best case runtime of insertion sort is linear, i.e. $\Theta(n)$. Therefore, there is no $\Theta(n^2)$ bound on all inputs, since that would require $\Omega(n^2)$ on all inputs.

This is just one example proving that while $O$-bounds on the worst-case translate to all-case, but $\Omega$-bounds (and therewith $\Theta$-bounds) do not. (Which is, of course, the point in the text.) You can also investigate this mathematically by unfolding the definitions.


Counting the number of multiples of number A that perfectly divides the number B

Start by checking whether $A$ divides $B$. If it doesn't, we're done, the answer is $0$. If it does, let $C = \frac{B}{A}$. The numbers you're looking for are all of the form $AM$ where $M$ divides $C$, so all you need is the number of divisors of $C$.

Let $C=p_0^{c_0}...p_n^{c_n}$ be the prime decomposition of $C$. The number of dividers of $C$ is then $\prod\limits_{i}(c_i+1)$, so the problem boils down to the prime decomposition of $C$, which can indeed be done in $O(\sqrt{C})$:

residue = C
divider = 2
number_of_prime_dividers = 0
factors = empty array
while((residue >= divider) and (divider <= sqrt(C))
{
    if(divider divides residue)
    {
        number_of_prime_dividers = number_of_prime_dividers +1
        factors[number_of_prime_dividers] = 0
    }
    while( divider divides residue )
    {
        residue = residue / divider
        factors[number_of_prime_dividers] = factors[number_of_prime_dividers] + 1
    }
    divider = divider + 1
}
if(residue != 1)
{
    number_of_prime_dividers = number_of_prime_dividers +1
    factors[number_of_prime_dividers] = 1
}

This algorithm works because by construction, every time dividerdivides residue, then it means that divideris prime (if divider is composite then all the factors of divider are strictly smaller than divider and thus have already been removed from residue). Once we reach sqrt(C), if residue != 1 we know that residue is prime, which concludes the decomposition.


How to produce all the numbers in a range [0,1,...,n] for which if 0<=k<=n, then for a positive integer x, the expression: k & x = k?

This answer shows how to find all values of $x$ satisfying the equation for fixed $k$. The OP asked for all values of $k$ satisfying the equation for fixed $x$, but the same methods work for both problems.

First of all, we have $k \& x = k$ if $x_i = 1$ whenever $k_i = 1$. If we think of $k,x$ as sets whose elements are the 1 bits, then the equation becomes $k \cap x = k$, which is equivalent to $k \subseteq x$, and so if $i \in k$ (i.e., $k_i=1$) then $i \in x$ (i.e., $x_i=1$).

In order to generate all solutions $x$ in the range $0,\ldots,n$, it suffices to generate all solutions in increasing order; we can stop once reaching a solution which is larger than $n$.
How do all solutions look like? Let the 0 bits of $k$ be $i_0 < i_1 < \cdots < i_\ell$. Then the solutions are
$$ k + \sum_{j=0}^\ell b_j 2^{i_j}, $$
where $b_j \in \{0,1\}$; we can replace addition equivalently with bitwise OR. Moreover, if we think of $b_\ell\ldots b_0$ as a binary number, then the mapping from $b_\ell \ldots b_0$ to $k + \sum_j b_j 2^{i_j}$ is monotone: as we go over all values of $b_\ell \ldots b_0$ in increasing order, the values of $k + \sum_j b_j 2^{i_j}$ appear in increasing order. This leads to the following algorithm:

Let $b \gets 0$.
Compute $x = k + \sum_j b_j 2^{i_j}$, where $b_j$ is the $j$th bit of $b$.
If $x \leq n$, output $x$, increase $b$ by 1, and go back to 2. Otherwise, halt.


Condition of square root algorithm (Newton's method)

Try calculating the square root if 1e-100 with the changed loop condition and see what result you get. Then try calculating the square root of 1e100. Do you run into any problems?

This is numerical mathematics, limits won’t work well. Print out the value of t -c/t and check whether it actually converges, and check if it converges to 0. For some different values if c.

From a wiser man than me: The problem are not the things we don’t know. The problem are the things we know that ain’t so.


Your problem is known as 3-dimensional matching, or 3DM. It is one of the 21 problems proved to be NP-hard in Karp's original paper (number 17 on his list).


Also by definition of $G$, some formula holds in every state.

Well, $\sf true$ holds in every state. I'm unsure about why you mention $G$ here.

  So if globally $\phi$ holds until we see $\psi$ does it make every state after it true?

A state can not be true or false, like 42 can not be true or false. This is meaningless.

  is it correct to say that also $G(\phi U \psi)U\phi \equiv G(\phi U \psi)  $

Take $\phi = \sf false$ and $\psi = \sf true$. Then, $G(\phi U \psi)U\phi$ is equivalent to $\sf false$, and $G(\phi U \psi)$ is equivalent to $\sf true$.


3SAT with an oracle for expanding the clauses

Your question seems closely related to the question of whether $NP=coNP$. It seems that the existence of such an oracle would imply $NP=coNP$ since the oracle would give you a polynomial certificate for "no"-instances of $SAT$.

I don't think this would be a viable way to show $P\not = NP$ since all you'd be showing is that there's no way to expand clauses in polynomial time, but that does not rule out other approaches for solving $SAT$.


fast and stable x * tanh(log1pexp(x)) computation

With some algebraic manipulation (as pointed out in @orlp's answer), we can deduce the following:
$$f(x) = x \tanh(\log(1+e^x)) \tag{1}$$
$$ = x\frac{(1+e^x)^2 - 1}{(1+e^x)^2 + 1} = x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2}\tag{2}$$
$$ = x - \frac{2x}{(1 + e^x)^2 + 1} \tag{3}$$
Expression $(3)$ works great when $x$ is negative with very little loss of precision. Expression $(2)$ is not suitable for large values of $x$ since the terms are going to blow up both in the numerator and denominator.
The function $(1)$ asymptotically hits zero as $x \to-\infty$. Now as $x$ becomes larger in magnitude, the expression $(3)$ will suffer from catastrophic cancellation: two large terms cancelling each other to give a really small number. The expression $(2)$ is more suitable in this range.
This works fairly well until $-18$ and beyond which you lose multiple significant figures.
Let's take a closer look at the function and try to approximate $f(x)$ as $x \to-\infty$.
$$f(x) = x \frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2}$$
The  $e^{2x}$ will be orders of magnitude smaller than $e^x$. $e^x$ will be orders of magnitude smaller than $1$. Using these two facts, we can approximate $f(x)$ to:
$f(x) \approx x\frac{e^x}{e^x+1}\approx xe^x$
Result:
$f(x) \approx \begin{cases}
xe^x, & \text{if $x \le -18$} \\
x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2} & \text{if $-18 \lt x \le -0.6$} \\
x - \frac{2x}{(1 + e^x)^2 + 1},  & \text{otherwise}
\end{cases}
 $
Fast CUDA implementation:
__device__ float mish(float x)
{
    auto e = __expf(x);
    if (x <= -18.0f)
        return x * e;

    auto n = e * e + 2 * e;
    if (x <= -0.6f)
        return x * __fdividef(n, n + 2);

    return x - 2 * __fdividef(x, n + 2);
}

EDIT:
An even more faster and accurate version:
$f(x) \approx \begin{cases}
x\frac{e^{2x} + 2e^x}{e^{2x} + 2e^x + 2} & \text{$x \le -0.6$} \\
x - \frac{2x}{(1 + e^x)^2 + 1},  & \text{otherwise}
\end{cases}
 $
__device__ float mish(float x)
{
    auto e = __expf(value);
    auto n = e * e + 2 * e;
    if (value <= -0.6f)
        return value * __fdividef(n, n + 2);

    return value - 2 * __fdividef(value, n + 2);
}

Code: https://gist.github.com/YashasSamaga/8ad0cd3b30dbd0eb588c1f4c035db28c
Benchmarks with other implementations: https://github.com/YashasSamaga/ConvolutionBuildingBlocks/tree/master/mish
$$\begin{array}{c|c|c|c|}
 & \text{Time (float)} & \text{Time (float4)} & \text{L2 norm of error vector} \\ \hline
\text{mish} & 1.49ms & 1.39ms & 2.4583e-05 \\ \hline
\text{relu} & 1.47ms & 1.39ms & \text{N/A} \\ \hline
\end{array}$$


Which calculus is based on first-order functions and is Turing complete?

There are many, but I think the most famous one µ-recursive functions. It describes functions from $\mathbb{N}^{(\mathbb{N})}$ to $\mathbb{N}$, i.e. from tuples of naturals to naturals. This can be transformed into a theory of functions from $\mathbb{N}$ to $\mathbb{N}$ by composing with an encoding of tuples; I think the reason it isn't commonly presented that way is that it doesn't look neat.

µ-recursive functions are defined as follows:

All constant functions are µ-recursive.
The successor function ($S(n) = n+1$) is µ-recursive.
Projections ($\pi_i(n_1,\ldots,n_k) = n_i$) are µ-recursive.
Composition: if the $f_i$ and $g$ are µ-recursive then $(n_1,\ldots,n_{k_1+\ldots+k_m}) \mapsto g(f_1(n_1,\ldots,n_{k_1}), \ldots, f_m(n_{k_1+\ldots+k_{m-1}+1},\ldots,n_{k_1+\ldots+k_m}))$ is µ-recursive.
Primitive recursion: if $f$ and $g$ are µ-recursive then the function $h$ defined by $h(0,n_1,\ldots,n_k) = g(n_1,\ldots,n_k)$ and $h(n+1,n_1,\ldots,n_k) = f(n,n_1,\ldots,n_k,h(n,n_1,\ldots,n_k))$ is µ-recursive.
Minimisation: if $f$ is µ-recursive then so is the function that maps $n_1,\ldots,n_k$ to the smallest $x$ such that $f(n_1,\ldots,n_k,x) = 0$.

Note that in the definition of the minimisation operator, it is possible for $x$ not to exist. In this case the resulting function is partial. This calculus thus defines partial recursive functions.

If you restrict the calculus to total functions, you get the recursive functions, with the same computing power as Turing machines.

The minimisation operator is usually written $\mu$ and gives the calculus its name. If you omit it, the resulting set of functions are exactly the primitive recursive functions (indeed that's a convenient way to define them).


Prove that, if deg(v) ≥ (n−2)/3 for every vertex v in G, then G contains at most two connected components

Assume there are are at least 3 connected components. Then there must be a connected component of size $\le\frac{n}{3}$. Let $v$ be a vertex in that connected component. By assumption we have $deg(v)\ge\frac{n-2}{3}$. Since the size of that connected component is at most $\frac{n}{3}$ than it must be that $deg(v)\le\frac{n}{3}-1=\frac{n-3}{3}$. So we get both $deg(v)\ge\frac{n-2}{3}$ and $deg(v)\le\frac{n-3}{3}$, a contradiction. Thus, there must be at most 2 connected components.


$M_2$, while running on $w$, calls $M_1(w)$ as a subroutine. So if $M_1(w)$'s output is stored on $M_2$'s working tape then it requires polynomial space, not logarithmic space. So, $M_2$ does not work in logarithmic space no matter it is deterministic or nondeterministic.

Of course you could design your machine $M_2$ so that $M_1(w,i)$ would return $i$th bit on demand (on each call). In this case it would work in logarithmic space. But it depends on the problem you solve.


Proof that Hamiltonian cycle/circuit with a specified edge is NP-complete

Given: a graph $G$, an edge $e$, and a length $k$.

Optimization problem output: a cycle of length $k$, containing $e$ (or none, if there is none).

Decision problem output: "yes" if such a cycle exists, "no" otherwise.

Now, it is obviously in NP, as you can simply check any answer to the optimization problem; see if it is a cycle, see if the cycle contains $e$, and check that the length of the cycle is $k$.

There are two easy ways to prove it is NP-hard. Imagine you had a magic algorithm, ${\rm M{\small AGIC}}(G,e,k)$, that can answer this for you.

Method 1 hint: In the k-SAT to DHC  (directed Hamiltonian cycle) reduction, aren't there some edges that must occur? (and don't these carry over to UHC (undirected Hamiltonian cycle)?)

More hints (mouseover):

   The reduction from k-SAT to DHC (directed Hamiltonian cycle) involved a root node, and a sink node. The sink node has an edge to the root node; and it is the only incoming edge to the root node; hence, the sink-root edge must be used in the DHC.

 Furthermore, in the reduction from DHC to UHC, each node gets split into 3 nodes, and the middle one is connected to the two outer ones with a single edge. Well, as a general rule, any degree-2 nodes make it easy to solve this problem (because the cycle must pass through it).

Method 2 hint: What happens if you pick a node. The Hamiltonian Cycle must pass through one of its edges. How many edges can a node have?

More hints (mouseover):

   Maybe you can solve a regular UHC with some calls to ${\rm M{\small AGIC}}(G,e,k)$.


Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages

It's not needed for the proof. You can prove the lemma without this condition. Adding this condition makes the statement stronger and so more useful.

The intuition here is that if a DFA has $p$ states and there is a list of $p+1$ of them, then the list must contain two states which are the same. The string $x$ is the part that stretches from the beginning of the input to the first occurrence of the double state, and the string $y$ stretches until the second occurrence. By considering the first repeat we can guarantee that $|xy| \leq p$, since after reading $p$ characters we have seen $p+1$ states.


Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B

The easy solution is to add an edge between $s$ and $u$ with infinite weight and $t$ and $v$ with infinite weight.
Note though that this doesn't mean that $s$ and $u$ will be connected in $G[A]$.


weighted-clique to vertex cover reduction

Let $G=(V,E)$ be an unweighted graph (think of all the edges as having weight $1$), $n=|V|$, and $\bar{G}$ be the edge-complement of $G$.

Now, $C$ is a vertex cover of $G$ iff $\bar{C} = V \setminus C$ is an independent set of $G$, that is, iff $\bar{C}$ is a clique of $\bar{G}$.

When you combine this with the fact that a clique of size $k$ has $\binom{k}{2} = \frac{k^2-k}{2}$ edges you get: "There is a vertex cover of size $k$ in $G$ iff $\bar{G}$ contains a clique of size $a = n-k$ and weight $b = \binom{n-k}{2}$."

In fact, as far as this reduction is concerned, you can drop either the size or the weight constraint from your clique problem since one implies the other.


Is it possible to denote "any single alphabet symbol" in an FSA state diagram?

The formal representation of an automaton is the tuple giving its state set, alphabet, transition function, start state and set of accepting states. The diagram is not a formal representation: it's just an informal way of showing what the automaton does.

As such, you can label the arrows however you want, as long as it's clear what each label means. If you think a label might be unclear, you can always add a caption to your diagram that explains what it would mean.

"." is a poor label, since it's too easy to miss. "*" is a confusing label since, in regular expressions, "*" means "any number of times", not "any symbol". Since it's quite common to see arrows in automata labelled, e.g., "$0,1$", I'd probably label the arrow "$\sigma_1, \dots, \sigma_k$" and note in the caption that $\Sigma = \{\sigma_1, \dots, \sigma_k\}$. Or you could just label the arrow "$\Sigma$".


Inclusion of complexity classes (Deterministic Turing Machine)

Expanding on the comments, the idea is that if a Turing machine has $M$ possible configurations then if it halts, it must do so within $M$ steps. The reason is that once the machine has stepped through $M+1$ different configurations, it must have stepped on the same configuration $C$ twice. Since the machine is deterministic, each time it reaches configuration $C$, it will work its way in the same manner and reach $C$ again, and again, and again, indefinitely.

How many different configurations are there? Suppose the tape alphabet is $\Sigma$ (include the blank symbol), the space is $S$ (assume for simplicity that the tape is one-way infinite so there is a unique chunk of space $S$), and there are $N$ states. Then the number of configurations is $NS|\Sigma|^S$, since a configuration is given by the state, the position of the head, and the contents of the tape. We can write this bound as
$$ NS|\Sigma|^S = 2^{\log N + \log S + (\log |\Sigma|) S} \leq 2^{c(1+\log S + S)} $$
for $c = \max(\log N, \log |\Sigma|)$. Assuming $S \geq 2$, we can further simplify this to $2^{c(1+\log S+S)} \leq 2^{c'(\log S+S)}$ for $c' = 2c$.


To check whether a given number has been computed previously or not

You could use a hashtable to keep track of all values you've seen before.  (You could also use a balanced binary tree data structure, but it will probably be less efficient in practice, due to the overhead of the pointer traversals.)

If you don't mind occasional false positives, you could use a Bloom filter, and that might be even more efficient -- at the cost of occasionally declaring "I've seen this number before!" when you actually haven't.

Questions about specific C++ libraries are off-topic here but can be asked on Stack Overflow once you know what data structure you want to use.


The meaning of
$$ \exists u A(u) \land \exists n S(n,\text{available}) $$
is "there exists an active user, and there exists a network link which is available". The conditioning is missing here.

If $P = \exists u A(u)$ and $Q = \exists n S(n,\text{available})$, then we are trying to model "if $P$ then $Q$", whose formal form is $P \rightarrow Q$, whereas your answer is $P \land Q$.

In particular, if there doesn't exist an active user, then $P \land Q$ is always false, whereas $P \to Q$ is always true.


How do proof assistants nowadays avoid floatpoint error?

It depends on whether you want to "simply" reason about the properties of real numbers, or if you want to perform actual calculations.

If you want to prove things about their general properties, then using Dedekind cuts is feasible.

If you want to compute actual numerical things, then you need a numerical representation of the cut, and then you're back to some computable representation of (some of) the reals (you can't get all of them). It doesn't strictly have to be floating point numbers - you could use arbitrary precision arithmetic for example - more accurate but slower in general.

Your type however seems to be aiming to represent the Rationals, for which floating point numbers are unnecessary, you could just have a type with one constructor: nat -> nat -> Q.


It usually doesn't matter, since we're usually only interested in the order of growth of the number of steps.  As long as we both agree that evaluating A[i] is a constant number of steps, independent of i, it doesn't actually matter what that constant is and we don't need to agree that it's the same constant.  We'll both agree that the algorithm is, say, $\Theta(n^2)$, even if I think the running time is $45n^2 + 16n + 18$ and you think it's $68n^2+25n+21$.  (And, in reality, neither of us is likely to be able to evaluate the running time to that level of precision.

So, it's usually fine to say that A[0] is a single step, as is A[5] (any sane compiler would compute "five cells beyond A[0]" at compile-time anyway) and A[i] where i is some variable. It won't make any difference to most analyses if you say that A[5] and A[i] are two operations due to having to compute the offset.

In some models of computation, things might be a bit more complicated because, if i is an arbitrary integer, it might not be sensible to assume that you can manipulate it in a constant number of steps. For example, on a standard Turing machine, you need to  read $\log\texttt{i}$ tape cells just to know what i is. But that doesn't look much like what a real computer does.