Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$

If you're allowed to make multiple passes through the data, one efficient approach is to use QuickSelect to find the value of the $k$-th largest element, then follow with a linear scan that outputs all elements that are larger than it.

This is more or less a more carefully-worked out version of the kind of approach you seemed to be considering.

See also https://en.wikipedia.org/wiki/Selection_algorithm.

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another possible approach would be to take a sorting network, which is a hardware circuit that sorts all of the values.  Then, throw away all but the last $k$ outputs, and keep only the gates they depend on.  You might be able to throw away a non-trivial fraction of the sorting network -- I haven't tried to work out how much.  This would solve the partial sorting network, and could potentially be hardware-friendly.

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another approach is to do something like merge sort, but where you only keep the top $k$ elements in each list at each stage.  In other words, split your data so that each processor receives an equal number of items.  Have each processor find the top $k$ of its elements (say, using a priority queue or any other method).  Then merge lists recursively, where each merge operation merges two or more lists of size $k$ and outputs only the first (largest) $k$ elements of the result.  This might work very well for out-of-cache (too-large-to-fit-in-main-memory) situations, or for parallel computing.  If you can fit $B$ items in cache/memory, then each merge step merges $B/k$ lists, so the number of rounds is $\lg_{B/k} (n/B)$.


Graph canonization is a a procedure that takes a graph $G$ and returns an isomorphic graph $C(G)$, we the promise that $C(G) = C(H)$ iff $G$ and $H$ are isomorphic. We call $C$ a canonical form.

One possible canonical form is the lexicographically smallest adjacency matrix. Given an ordering of the vertices, we can serialize the adjacency matrix as a binary string. Given a graph $G$, we choose the ordering leading to the lexicographically smallest such string, and then order the graph accordingly to form $C(G)$. It is not hard to check that this is a canonical form.

The algorithm, as stated, has exponential complexity, so isn't practical. There might be faster ways to compute this canonical form, or they might be other canonical forms which are easier to compute. Notice, however, that canonical forms can be used to solve graph isomorphism, and so finding an efficiently computable canonical form is hard and might be impossible (depending on the meaning of efficient).

It is still possible that there is an easily computable canonical form that works for most graphs, just like graph isomorphism is easy for most graphs. For more on this topic, see this question, and particularly the survey by McKay and Piperno mentioned in my answer there.


What's the name of this tree-like data structure?

This is simply a tree, where all elements are unique.  I'm not aware of any special name.


The language $L = L_1 \cup L_2$ consists of all pairs $\langle M,w \rangle$ where $M$ is a description of a Turing machine and $w$ is a word. This language is not necessarily regular (it depends on the exact encoding), but it is certainly decidable. All you have to do, given an input, is to decide whether it is of the form $\langle M,w \rangle$.

Note that deciding $L$ bears no relation to the halting problem. My description of $L$ doesn't refer to whether $M$ halts on $w$ or not. Here is a similar example. Let $f$ be an uncomputable integer-valued function. The function $g := 1-f$ is uncomputable as well, yet $f + g$ is computable.


I need clarification about DFA's and DFA acceptable languages

$Doubt-1$:  "But wouldn't a simple DFA that has only one state that is a final state and loops back to itself on all inputs accept that language?"

No, the DFA you are thinking about as below: accepts $(a + b)^*$ that is "all possible string consists of symbols '$a$' and '$b$', including $ε$ string".

     __
     ||  a, b
     ▼|
––►((Q0))

Q0 is both initial and final state

Language accepted by this DFA is superset of language $L = \{ a^nb^n$ | $n > 0  \}$  and hance also accepts all strings in $L$.

The concept you are missing is:
 "An automata $A$ for some language $L$ must accept $\textit{exactly}$  language $L$, neither a subset nor a superset of $L$".

Hance DFA above is not a finite representation of language $L = \{ a^nb^n$ | $n > 0 \}$.

  $Doubt-2$:  "Also in class we discussed how the complement of a DFA acceptable language is also DFA acceptable simply by swapping the final states and the non-final states".

Note: To construct new complement DFA $D$, old-DFA $A$ must be a complete, means there should all possible outgoing edge from each state (or in other words δ should be a complete function).
Read "Complement DFA for Regular Expression $(00 + 1)^*$" to learn how to consturct complement DFA.

  $Doubt-3$:   But if you had the language $L = \{ a \}$, over the alphabet $\{ a, b \}$, then obviously $L$ is DFA acceptable, but the complement of $L$ is $\{ a, b \}^* - \{ a \}$, which includes $\{ ab, aabb, aaabbb, \ldots \}$.

As you already know complement of a regular language is regular (DFA exists for regular language and you know how to make DFA for complement regular language), so new language $L^" $ = $\{ a, b \}^* - \{ a \}$ is a regular language.

And language $L^" $  is a superset of language $\{ a^nb^n$ | $n > 0 \}$.

The concept you are missing is that you don't know:

  $Doubt-4$:   "What is called regular language?" And Why a languages like $(a + b)^*$  is regular? But language $\{ a^nb^n$ | $n > 0 \}$ is not a regular language**

A language (a set) $L$ is called Regular Language, if its require bounded (finite) amount of information at any instance of time while processing a strings in language $L$.

What is bounded information?
For example: Consider a fan switch for on-off. By viewing fan-switch we can say whether fan is in on or off state (this is bounded or limited information).
But we can not know that how many times a fan has been on-off in past! (to memorized, it requires a mechanism to store unbounded amount of information to count how many times  – e.g. some kind of meters, we have in our car/bike).

To understand how states are uses as memory element read this answer, you may also like to read: How to write regular expression for a DFA

Language $\{ a^nb^n$ | $n > 0 \}$ is not a regular because here $n$ is unbounded. To verify string in language $a^nb^n$ we have to remember how many '$a$' has been came and this required a infinite memory to count because number of '$a$' s in string that can be infinity large.
(hence an automata can only capable to process strings of $a^nb^n$ if it has infinite memory e.g PDA).

Whereas $(a + b)^*$ is of-course a regular by its nature, because there is bounded restriction that "string consists of only symbol '$a$' and '$b$'".
 And strings of this language can be easily processed (or recognized) by an automata in which we have finite memory that is finite automata. Yes, in finite automata we have finite memory in terms of states (The word "Finite" significance of the presence of 'finite amount of memory' in the form of finite number of states $Q$).

Summarize:

Memory in finite automata is present in the form of states $Q$ only and according to automata principal: any automata can have only finite set of states. hence finite automata has finite memory, this is the reason automata for regular language is called finite automata. You can think a finite automata like CPU without memory, that has finite  register to remember its internal states.

Finite State  –► Finite Memory  –► Only language can be process for which finite memory need to store at any instance of time while processing the string: –► that language is called Regular Language

Absence of external memory is limitation of finite automate  –► or we can say limitation of class of language defined by finite automata that is called Regular language.

Side note::
*   Also a language { anbn | 10>100 n > 0 } is regular, a large set but regular because $n$ is bounded, hence finite automata and regular expression is possible for this language  – finite set is always regular.
*  There are infinite sets those are regular. Regular language of subset of all possible infinite set. Check this Venn-diagram.

So, if any time you need to proof that a language $L$ not a regular – before the go to use "formal tools" likes pumping lemma, first try to proof using fundamental definition of regular language.


Proving building a balanced BST out of sorted array is $\Theta(n)$

If you are allowed to use the master theorem then you can immediately conclude that $T(n)=\Theta(n)$ (since $n^{\log_2 2} = n = \omega(1)$).

If you are not allowed to use the master theorem then you can write this recurrence instead:
$$
T(n) \le 2T(\lfloor n/2 \rfloor) + c,
$$
where $c > 0$ is an absolute constant and $T(1) \le c$.

Then you can prove by induction that $T(n) \le 2cn - c$.
The base case is $n=1$ and is trivial since $T(1) \le c = 2cn - c$.
Consider now $n>1$ and suppose that the claim holds up to $n-1$, we will prove that it also holds for $n$:
$$
T(n) = 2T(\lfloor n/2 \rfloor) + c \le 2(2c\lfloor n/2 \rfloor-c) + c \le
2cn - 2c +c=2cn-c.
$$


Efficient simulation of an NFA, while preserving the paths to the accept states

There is no need to construct the DFA. Instead, you can construct a dynamic programming table which answers the question "the NFA could be at state $s$ after reading the $k$th prefix of the word" (the parameters are both $s$ and $k$). In order to efficiently fill this table in the presence of $\epsilon$-transitions, you need to compute ahead of time the transitive closure of the $\epsilon$-transitions. As you fill the table, you can include data that will allow you to reconstruct at least some of the accepting paths (or all of them, if you insist, though it will be more tricky to handle the $\epsilon$-transitions). The running time, however, won't be linear but more like $O(q^2m)$, where $q$ is the number of states; perhaps you could optimize this further for sparse NFAs, but probably not to $O(m+n)$.


$T \equiv \lambda x. \lambda y. x$, which means it is a $\lambda$-function of two arguments, returning the first one, so $(T\ T\ F)$ $\beta$-reduces to $T$, which can be shown more formally as follows.

$$T\ T\ F \equiv (\lambda x. \lambda y. x)\ T\ F \to_\beta
(\lambda y. T)\ F \to_\beta
T$$


This can also be proved easily using Myhill-Nerode theorem.

Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose  $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^*
 ,L(xz) \neq L(yz))   $$ where S is an infinite set. Then L is not a
regular language.

(Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.)
For the given problem, We have $L=\{w:\#_a(w)=\#_b(w)\}$.
Take $S = a^*$ (note: the set $S$ is infinite).
Now take any two distinct elements from set $S$, $x=a^i$ and $y=a^j$,
and take $z=b^i$.
So $xz \in L$ and $yz \notin L$.
Hence, we will get an infinite number of distinct quotients as $S$ is an infinite distinctive set.
Thus, $L$ is not regular.


In order to compute the inverse of $a$ modulo $n$, use the extended Euclidean algorithm to find the GCD of $a$ and $n$ (which should be 1), together with coefficients $x,y$ such that $ax + ny = 1$. The inverse of $a$ modulo $n$ is thus $x$.

The extended Euclidean algorithm gives a constructive proof of Bézout's identity, which states that for all integers $a,b$ there exist integers $x,y$ such that $ax+by = \mathrm{gcd}(a,b)$. A different proof shows that the minimal positive value of $ax+by$ (over all $x,y$) is $\mathrm{gcd}(a,b)$.

The extended Euclidean algorithm works in greater generality, for any Euclidean domain. An important example is the ring of polynomials over a field.


Proving complexity of $T(n)=2T(n/3 + 1) + n$ non-Akra-Bazzi

You can use the variant by Leighton "Notes on Better Master Theorems for Divide-and-Conquer Recurrences". Lehman, Leighton and Meyer in "Mathematics for Computer Science"
on page 1019 state a simplified version: If you have $T(n) = \sum_{1 \le i \le k} a_i T(b_i n + h_i(n)) + g(n)$, where $a_i > 0$, $0 < b_i < 1$, $g(n) > 0$ such that $\lvert g'(x) \rvert$ is bounded by a polynomial, and $\lvert h_i(n) \rvert = O(n / \log^2 n)$, then is $p$ is the unique real such that $\sum_{1 \le i \le k} a_i b_i^p = 1$, then:

$$
T(n) = \Theta\left(
               n^p \left(
                      1 + \int_1^n \frac{g(u)}{u^{p + 1}} d u
                   \right)
             \right)
$$

Your $g(n) = n$ certainly qualifies. With $a_1 = 2$, $b_1 = 1/3$, $h_1(n) = 1$ satisfies the condition, you get:

$$
  2 \cdot 3^{-p} = 1
$$

from which $p = \log_3 2$, so that:

$$
T(n) = \Theta\left(
               n^{\log_3 2}
                  \left(
                      1 + \int_1^n u^{- \log_3 2} d u
                   \right)
             \right)
     = \Theta(n)
$$


How to prove $T(n) = 2T(n/2) + n/\log(n)$ can't be solved using the Master Theorem?

Your recursion can be written as:
$$
T(n) = aT(n/b) + f(n),
$$
where $a=b=2$ and $f(n) = n \log^{-1} n$. Defining $c_{crit} = \log_b a = 1$ you can see that $f(n) = \Theta( n^{c_{crit}} \log^k n)$ for $k=-1$, therefore case 2b of the Master Theorem applies.
The solution to the recurrence is therefore:
$$T(n) = \Theta( n^{c_{crit}} \log \log n ) = \Theta( n \log \log n).$$


$\sqrt{n} = \Omega(3^{\log{}n})$ is not true? Why?

We'll start with some arithmetic, and assume the base of the logarithm to be $x$. First, remember the log law:
$$
\log_{a}(b) = \frac{\log_{c}(b)}{\log_{c}(a)}
$$
So
$$
\begin{array}{rl}
3^{\log_{x}(n)} &= 3^{\frac{\log_{3}(n)}{\log_{3}(x)}}\\
&=(3^{\log_{3}(n)})^{1/\log_{3}(x)}
&=n^{1/\log_{3}(x)}
\end{array}
$$
Whether $n^{\frac{1}{2}}$ is in big-omega of this then depends on what $x$ is.

If we make the right and proper computer science assumption that the base 2 logarithm is the only logarithm (that was a joke of course), then $1/\log_{3}(x)=1/\log_{3}(2)\approx 1.6$, which is certainly bigger than $1/2$.

You'd need $x\geq 9$ for the statement to be true.


n closest points in a set of lat/long coordinates

Your problem (at least the second variant) is known as 2D range searching. Commonly used data structures are range trees and k-d trees. Searching for range searching on the web will open you a window into the area. These lecture notes come up, for example.


Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems

As I have hinted at in the comments, that your reduction exists is not at all surprising. As in my answer to your previous question, your "Expand and simplify" part takes potentially exponential time and, thus, does not qualify as a polynomial-time reduction (which is the standard notion used to compare the classes in question). Exponential-time reductions here are irrelevant because both $\mathsf{NP}$ and $\#\mathsf{P}$ are contained in $\mathsf{EXP}$, so the reduction is powerful enough to solve the problems it should be reducing.

As to address the question in the title, notice the following: Let $P \in \mathsf{NP}$ be some problem, $S_P$ the solution set associated with $P$ (i.e., the $\{0,1\}^\ast \times \{0,1\}^\ast$ relation which, for instance, associates each $x \in P$ with its (poly-time verifiable) solutions), and $\#S_P\colon \{0,1\}^\ast \to \mathbb{N}_0$ be the counting problem associated with $S_P$, that is, $\#S_P(x) = |S_P(x)|$. For $P = \mathsf{SAT}$, for example, $S_P$ is simply the relation of formulas to their satisfiable assignments, and $\#S_P$ the number of satisfiable assigments. Then you can recast $P$ as the (decision) problem $\{ x \mid \#S_P(x) \ge 1 \}$. This means that having a procedure which counts solutions (i.e., computes $\#S_P \in \# \mathsf{P}$) directly yields something which decides $P \in \mathsf{NP}$.

Not only that, but notice that above we do not even actually use the value $\#S_P(x)$ other than to test that it is not zero. It is conceivable that we can use that accurate value towards solving problems much harder than $\mathsf{NP}$ (e.g., as Toda's theorem tells us; see David Richerby's answer). This gives us enough reason to believe that problems in $\#\mathsf{P}$ are, in general, much harder than those in $\mathsf{NP}$ (the most conspicuous candidates being the $\#\mathsf{P}$-complete problems).


Eliminating useless productions resulting from PDA to CFG converison

It is not very clear what you wish to achieve. Do you wish to reduce the number of productions to the minimal possible? Do you only wish to avoid productions that are "not helpful" i.e., never appear in any valid derivation?

The first question seems difficult (e.g., This Work shows that it is NP-hard to approximate the length of the smallest grammar within a certain constant factor)

If you talk about the second issue, more things can be done. You should look on methods for converting grammar into a normal form (like Chomsky- or Greibach- normal form), since usually the first step in those conversions is to eliminate any unnecessary productions.

To be more specific, the most easy thing we can do, is to eliminate unreachable variables:

  For a given grammar $G=(V,T,S,P)$, we say that some variable $X \in V$ is unreachable if it cannot be reached from $S$, that is, there is no $\alpha \in (V \cup T)^*$ such that $S\to^* \alpha$ and $X\in \alpha$.

You can find unreachable variables by a straightforward BFS search starting from "$S$".

To complete the answer, let me also note that there are another type of variables, which we call unproductive (or "dead"). Those variables will cause the derivation never to terminate. Formally:

  We say that a variable $X\in V$ is unproductive if for any $\alpha \in (V\cup T)^*$ such that $X\to^*\alpha$, $\alpha$ has at least one variable, that is, $\alpha \notin T^*$.

For instance, if $S\to A \mid 1$ and $A\to A1$, then $A$ is unproductive—you can never get rid of it. Unproductive variables are also quite easy to find, and can be removed from the grammar (possibly along with some other productions, in which they appear on the right-hand-side.)


Count substrings with same first and last characters

You can do it in linear time. Loop over the characters of the string and count the frequency (how many times it appears in the string) of each distinct character. Then if a character has a frequency $n$ then the count of all contiguous substrings starting and ending with same character is $\frac{(n+1)n}{2}$ and finally sum up all counts.

Example 1: $abcab$.
Frequencies: $f(a)=2, f(b)=2, f(c)=1$.
Counts: $3,3,1$ which gives $7$.

Example 2: $aba$.
Frequencies: $f(a)=2, f(b)=1$.
Counts: $3,1$ which gives $4$.

Example 3: $aaa$.
Frequencies: $f(a)=3$.
Counts: $6$ which gives $6$.

Example 4: $abc$.
Frequencies: $f(a)=1, f(b)=1, f(c)=1$.
Counts: $1,1,1$ which gives $3$.

NOTE:
$n*(n+1)/2$ is deduced this way:

Suppose you have this string $abcaba$ where first $a$ can be matched with second a at index 3 (0 indexed array) and also third $a$ at index 5.

frequency of $a$ is 3 so for first $a$ we will get 3-1 = 2 continuous substrings.

for second a we get 2-1 = 1 continuous substring

We are seeing a pattern as this: n,n-1, n-2.....0

This leads to the formula n*(n+1)/2 as we also need to consider individual $a$'s.

2 + 1 + 3 times $a$ = 6

Same is true for other characters in the string.


Filling Rows of a Matrix Subject to Conditions

If you are allowed to repeat rows, then a simple solution is to repeat the row $(N,0,0,0)$ as many times as needed.

If you are not allowed to repeat rows, this should also be pretty easy to solve.
This sounds like an exercise where you learn by doing, so I don't want to spoil it by giving away the answer, but I'll give you some tips and suggestions that will help you develop an answer:

What are the requirements for a row to be valid?  If $(w,x,y,z)$ are the four numbers in a row, what are the requirements on $w,x,y,z$ for this row to be allowable?
If I have one candidate row that meets all the requirements, and another candidate row that also meets all the requirements, can I put the first one in the first row of the matrix and the second row of the matrix?  Will that always be valid, or are there any constraints where my choice of the first row of the matrix restricts what I'm allowed to put in the second row of the matrix?  (If there are any restrictions, make sure you understand and can state precisely exactly what they are.)
How many possible ways are there to choose a single row that meets all of the requirements?  Hint: this is a standard problem in combinatorics/counting.  If you are in a computer science-oriented course on counting, your textbook will probably include a worked-out problem where it shows how to count the number of ways to place $k$ balls into $n$ bins with replacement, when order does not matter.  Make sure you understand the solution to that -- you might find it helpful.
How many different rows do you need?  Compare this to your answer to #2 above.  Relevance: If you need more rows than there are possibilities, and you need them to all be different, you're hosed.  If there are more possibilities than you need to list in your matrix, you can pick any subset.
How would you enumerate all valid rows?  You probably want to use some nested loops, e.g., loop over some range of values of $w$, and for each such $w$, loop over some range of values of $x$, and so on.  What range of values should you use for $w$?  (What values of $w$ are allowable?)  What range of values should you use for $x$?  (Since this is a nested loop, your range of values for $x$ is allowed to depend upon $w$.)  Fill out the rest of the details.

Update: Here's an overview of how to enumerate over these possibilities.  (This is really more of a Stack Overflow question than a question for this site, to be honest.)  I suggest you use three nested loops: loop over $w$ (over the range $0\ldots N$), then loop over $x$ (over the range $0 \ldots N-w$), then loop over $y$ (over the range $0\ldots N-w-x$), then set $z=N-w-x-y$.  In other words:

for w=0,1,2,...,N:
    for x=0,1,2,...,N-w:
        for y=0,1,2,...,N-w-x:
            z = N-w-x-y
            append the row (w,x,y,z) to the matrix

To generalize this code to enumerate all valid rows with $k$ columns, you should probably ask on Stack Overflow, as that's a coding question.  But here's a tip.  Think about how you'd enumerate all possible values of a $d$-digit odometer.  You'd create an array $A[0\ldots d-1]$, initially all zeros, to hold the $d$ digits, and you'd increment through odometer values, one by one.  How do you increment an odometer value?  Start with your finger pointing to the rightmost digit.  Increment that digit; except that if it increments from 9 to 10, that digit has rolled over, so change the 10 to a 0, move your finger left one place, and repeat the whole process (until nothing rolls over).  In code, here's how you increment an odometer value:

for i=d-1,d-2,...,2,1,0:
    A[i] = A[i]+1
    if A[i] == 10:
        A[i] = 0  // roll-over
    else:
        break out of the loop

What does this have to do with your problem?  Think of the first $k-1$ columns of each row as an odometer value.  We're going to enumerate through them.  Except, now the condition for when a digit rolls over is different: instead of rollover happening when that digit goes from 9 to 10, it will instead happen when the sum of that digit and all digits to its left goes from $N$ to $N+1$.  Everything else remains the same.  So, enumerate all possible values for the first $k-1$ columns, in this way.  Then, you can fill in the $k$th column to whatever it needs to be to make sure the entire row sums to exactly $N$.  If this doesn't help you, you might need to ask a separate question on Stack Overflow.

Once you work through the answers to all of these questions, you should have a solution.  If you have gotten stuck, edit your question show us how far you got so far (e.g., which of these questions you've figured out how to answer), at what stage you've gotten stuck, and what you've tried at that stage.


Can an NFA have multiple accepting states?

Whenever one is in doubt about central notions, one must consult the definitions of them. You should do this yourself (I assume that you have a textbook at your disposal).

Below is Definition 1.37 from Introduction to the Theory of Computation by Michael Sipser:

A nondeterministic finite automaton is a 5-tuple $(Q,\Sigma,\Delta,q_0,F)$, where

$Q$ is a finite set of states,
$\Sigma$ is a finite alphabet,
$\delta: Q \times \Sigma_{\epsilon} \rightarrow \mathcal{P}(Q)$ is
the transition function,
$q_0 \in Q$ is the start state, and
$F \subseteq Q$ is the set of accept states.

Item 5 tells us that $F$ is just a set of states, which means that it can be the empty set, a singleton set or a set with several states as elements.


Why is it best to use a prime number as a mod in a hashing function?

Consider the set of keys $K=\{0,1,...,100\}$ and a hash table where the number of buckets is $m=12$. Since $3$ is a factor of $12$, the keys that are multiples of $3$ will be hashed to buckets that are multiples of $3$:

Keys $\{0,12,24,36,...\}$ will be hashed to bucket $0$.
Keys $\{3,15,27,39,...\}$ will be hashed to bucket $3$.
Keys $\{6,18,30,42,...\}$ will be hashed to bucket $6$.
Keys $\{9,21,33,45,...\}$ will be hashed to bucket $9$.

If $K$ is uniformly distributed (i.e., every key in $K$ is equally likely to occur), then the choice of $m$ is not so critical. But, what happens if $K$ is not uniformly distributed? Imagine that the keys that are most likely to occur are the multiples of $3$. In this case, all of the buckets that are not multiples of $3$ will be empty with high probability (which is really bad in terms of hash table performance).

This situation is more common that it may seem. Imagine, for instance, that you are keeping track of objects based on where they are stored in memory. If your computer's word size is four bytes, then you will be hashing keys that are multiples of $4$. Needless to say that choosing $m$ to be a multiple of $4$ would be a terrible choice: you would have $3m/4$ buckets completely empty, and all of your keys colliding in the remaining $m/4$ buckets.

In general:

  Every key in $K$ that shares a common factor with the number of buckets $m$ will be hashed to a bucket that is a multiple of this factor.

Therefore, to minimize collisions, it is important to reduce the number of common factors between $m$ and the elements of $K$. How can this be achieved? By choosing $m$ to be a number that has very few factors: a prime number.


Clock skew vs clock offset in the context of clock synchronization network protocols

The terms aren't exactly the same, although have some similarities.

Clock Skew - a skew in the clock signal is referred to a time gap between the expected arrival of the clock to it's actual arrival, the skew can be positive or negative.
This might also be called jitter, it may be considered as sort of instability parameter of your system.
Skew is measured in time units (i.e. ns, us, etc.)
When designing a synchronous system you must make sure that your system doesn't have timing violations due to clock skews.
Clock Offset - offset of the clock is a delay of a given clock source, it might be known, or unknown. Offset can be measured in time units or phase degree.
Many times clock offset is intentional, for instance it's very common for data to be synchronised to falling edge of a clock, in this case, the receiver of the data, might consider the clock to have an offset of 180 degrees.

Another popular case might be receiving data in a certain clock, for instance 100MHz, while your system also has 100MHz clock, the 2 clocks might have a very low jitter rate, but the offset between them is usually unknown, there are components that can compensate and "fix" the offset and synchronise clocks such as PLL's.

Hope it's more clear now.


Conditional lower bounds on the running time of the single source shortest path problem

I found a lower-bound on the decremental SSSP based on the online matrix vector hypothesis. Decremental SSSP is a dynamic version of SSSP where updates are edge-deletions. On the other hand, it is appearing clear to me, that typical conditional lower-bounds do not make sense for SSSP, since relevant conjectures show that the exponent can not be improved and do not exclude improvement of log factors. On the other hand, improving the exponent in SSSP means a sublinear algorithm which is excluded since the size of the input is a lower-bound on the running time of any problem.


Can PTAS $\epsilon$ parameter be dependent on the algorithm input?

If $A$ is an algorithm whose running time is $O(1/\epsilon)$, then if you substitute $\epsilon = 1/n$, its running time will be $O(n)$. This is a property of the particular algorithm $A$ rather than of polynomial time approximation schemes. We have absolutely no guarantee on the running time of a PTAS when $\epsilon$ is subconstant (i.e., when $\epsilon = o(1)$).
The running time of algorithms tends to depend on the input length (though it's not always the case), so I'm not convinced that $A$ really has running time $O(1/\epsilon)$.


Reconstructing a data table from cross-tabulation frequencies

We have $M$ columns $C_1, \dots, C_M$ in the original table, each with a finite set of distinct values $V_1, \dots, V_M$.

Given the cross-table frequencies $c_{i,j}(a,b)$ (frequency of $a$ in $V_i$ and $b$ in $V_j$ occurring together), proceed as follows:

Determine $V_1, \dots, V_M$ and denote $V_i = \{v^{(i)}_j \mid j \in [1,n_i] \}$ where $n_i = |V_i|$.
Solve the following integer program:

$\qquad\displaystyle \min \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1,\dots,i_M)} \\
     \qquad \begin{align}
       \text{s.t. } \sum_{i_1 = 1}^{n_1} \cdots \sum_{i_{l-1} = 1}^{n_{l-1}} \sum_{i_{l+1} = 1}^{n_{l+1}} \cdots \sum_{i_{r-1} = 1}^{n_{r-1}} \sum_{i_{r+1}  1}^{n_{r+1}} \cdots \sum_{i_M = 1}^{n_M} x_{(i_1, \dots, i_M)} &= c_{(l,r)}(i_l,i_r) \\
       \qquad \text{for all }
       1 \leq l < r \leq M, i_l \in [1,n_l], i_r \in [1,n_r], \\
       x_{(i_1, \dots, i_M)} &\in \mathbb{N} \\
       \qquad \text{for all } i_1 \in [1,n_1], \dots, i_M \in [1,n_M]
     \end{align}$

The $x_{(i_1, \dots, i_M)}$ now indicate which row should occur how often, and we get a solution with the minimum number of rows possible. If we can influence the search, we can abort as soon as we find any feasible solution.

This is not likely to be efficient, but there are honed solvers for integer programs around so it's simple to implement. It may be possible to use an LP-solver and round to a feasible solution.


Number of induced paths in an interval graph

Consider the following example:

Say the total number of intervals is $n$. To get from one red extremity to the other, you can take a path which alternates between green and blue intervals. Each of those paths is induced, and there are $2^\frac{n-2}{2}$ such paths. Thus, the number of induced paths between two vertices in an interval graph is not necessarily polynomial in the number of vertices.


How is tamper-proofing of software evaluated for effectiveness?

Unfortunately, we don't know of any way to reliably measure the effectiveness of software obfuscation schemes (or the security of pretty much anything else).  The best we can do is publish the scheme, wait for other researchers to try to attack it, and see what the best attacks that someone has been able to find are.

As you can imagine, there are many limitations and caveats with that approach.  How do we know whether anyone has tried to break it, or whether the right people with the right skills have tried?  Or maybe there is some devastating attack that no one has thought of yet, but might be discovered tomorrow.

Anyway, that's the approach typically taken in practical work on software obfuscation.  There is also theoretical work on software obfuscation, which tries to prove security theorems (under some complexity-theory assumptions about the hardness of some well-studied problems).  Unfortunately, at present there is a significant gap between practice and theory.  For the most part, the provably secure schemes aren't practical, and the practical schemes aren't provably secure.  There are exceptions, but they tend to be very special-purpose -- they can only obfuscate a small class of special programs -- and can't be used to obfuscate an arbitrary program.  The theoretical work is very interesting and has made many advances but still has a way to go before we can find a truly practical, provably secure, and general scheme for software obfuscation.

Finally, if you are interested in practical schemes for practical use, let me share one last caveat.  My personal perspective is that none of the practical schemes for software obfuscation appear to be terribly secure.  They provide a speedbump that will slow down an attacker or require some effort and skill to break, but I would not expect any of them to resist a dedicated, motivated attacker.  So, while they're fine if you just want to increase the cost of reverse-engineering, I wouldn't rely on them to hold up to serious attack.  That's just my own personal sense and opinion, which others in the field might not agree with.


MESI Protocol Invalid cache line is attempted to be stored?

INVALID means "not in the cache," so there is nothing to flush. When you mark a cache block as INVALID it means that the data and the tag are not relevant.

Similarly, for your second question.  The line is not in P2's cache, so it should treat the line the same way it treats any other cache miss: (if it's a snoopy coherence mechanism then it should broadcast a message to all the other caches.  If it's a directory based coherence mechanism then it should send a request to the directory.)


If A is mapping reducible to B then the complement of A is mapping reducible to the complement of B

As Dave said, it follows from a simple logical equivalence: $p \leftrightarrow q$ is the same as $\lnot p \leftrightarrow \lnot q$. Now put $p= w\in A$ and $q = f(w) \in B$.

$A \leq_m B$ means there is a total computable $f$ s.t. for all $w$,

  $w \in A \leftrightarrow f(w) \in B$.

By the argument above, this is the same as

  $w \notin A \leftrightarrow f(w) \notin B$.

Or equivalently

  $w \in \bar{A} \leftrightarrow f(w) \in \bar{B}$.

And therefore, the same $f$ shows that $\bar{A} \leq_m \bar{B}$.


Contract edges $(C,D)$ and $(G,H)$ - and you'll get $K_{3,3}$.


Predicate calculus- meaning of the word "any"

So I am assuming your question is: Why is the formula to "Anyone who buys any pumpkin either carves it or eats it."

$\forall x \forall y (\text{pumpkin}(y) \wedge \text{buy}(x, y) \implies \text{carve}(x, y) \vee \text{eat}(x, y)) $

instead of

$\forall x \exists y (\text{pumpkin}(y) \wedge \text{buy}(x, y) \implies \text{carve}(x, y) \vee \text{eat}(x, y)) $

The problem with your version is that there might be someone who buys a pumpkin and decides not to eat or carve it and this would contradict the statement that every bought pumpkin (by a person $x$) will be either carved or eaten.


Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

First, while the Gale-Shapely algorithm guarantees that at least one stable matching exists, it need not be unique$^*$.

However, note that when the male-optimal and female-optimal matchings are the same, the stable matching is indeed unique, as shown in this answer.

As the male-optimal and female-optimal matchings coincide, both can be considered the 'optimal' side and therefore is Pareto optimal for both sides.

Your third argument however, is incorrect. While it is true the matching is unique, this is under the assumption that all preferences are true. As this is not the case, we cannot use this fact to conclude strategy-proofness on both sides.

However, we have the stronger property that the female and male optimal matchings coincide. This again means that the properties the algorithm assigns to the male side automatically apply to the female side and therefore the matching is strategy-proof for both sides.

(Another way to argue is that any manipulation cannot give the woman them a better result than switching sides with the men. But they already have the result they would get by switching! So they cannot improve by manipulation.)

*: Further conditions for uniqueness are explored in a paper by Jan Eeckhout:

The 'sufficient' condition for uniqueness (Theorem 1) basically says that if we order all men and women and if

All women of rank $i$ prefer the man of rank $i$ to any man of higher rank; and
All men of rank $i$ prefer the woman of rank $i$ to any woman of higher rank.

Furthermore, the paper mentions that if we match among a total of $4$ or $6$ persons, these conditions are also necessary for uniqueness.

If we want to talk about a Nash-Equilibrium, we have to phrase the matching process as a game. We can consider all men and women to be 'players' and their 'strategy' to be the preference profile they submit (which may differ from their actual preference, which determines the payoff). A set of strategies is said to be a Nash-Equilibrium if changing a single strategy of a single player cannot improve the results for that player. As we know that the current matching process is strategy-proof for all players involved, improving on 'everyone reports truthfully' is impossible. So, in this sense, the 'everyone reports truthfully' set of strategies is a Nash-Equilibrium.

In fact, we can say that strategy-proofness of our matching means precisely that the 'every reports truthfully' is a Nash-Equilibrium in the associated game we defined.


DFA accepts common strings, reduction to NPcomplete

Your problem is actually not NP-complete (unless NP=PSPACE), though it is NP-hard. The problem is that the witness - the string in the intersection - could be very long.

Kozen showed that DFA-intersection is PSPACE-complete, which implies the preceding paragraph. For a very similar proof (of a different statement), see my writeup.


RAM can be accessed hundreds of times faster than a hard drive. Explain How?

Wikipedia has great information on this topic, but as a brief, simplified explanation, know that it boils down mainly to the involvement of mechanical moving parts in a traditional Hard Disk Drive (HDD).

The size of the addressing space in itself doesn't affect the access times. Otherwise you could theoretically build a very small hard-disk drive with only 4GB and expect it to run just as fast as your RAM chip. In reality that  is not possible.

Hard Disk Drives

All the data is read and written by the read and write heads, laying on the round disks that physically store all the data. Whenever data in a specific address is specified, the heads must move to the correct track (the time it takes is the Seek Time) and the disk must rotate until the requested sector is under the head (Rotational Latency). The time until both of these tasks are completed is the Access Time, and only then the data transfer can actually start.

A - Track ; C - (Track) Sector

RAM

In contrast, RAM cards have no such mechanical moving parts and therefore the time constraints are much lower. They are mainly there to allow proper synchronization of the electronic components that comprise the memory card and ensure that it works reliably.

SSD

You probably also heard of the term Solid State Drive (SSD). Seagate recently manufactured such a drive with 60TB capacity, and its access times are still much shorter than those of hard-disk drives. How? Like RAM chips, they have no moving parts.


Your problem is NP-hard, by reduction from set cover. Given an instance of set cover with universe $V$, sets $U$ and number $n$, draw an edge between a set and a point if the set contains the point. Let $v_\min = 1$ and $v_\max = |U|$. A subset $U'$ satisfies the $v_\min,v_\max$ constraints iff it is a set cover. So if there is a set cover $W$ of size $m \leq n$, you can complete it to some $U'$ of size $n$ by adding $n-m$ sets and get a solution to your problem. Conversely, any solution to your problem is a set cover of size $n$.

Set cover is also hard to approximate better than $\log n$ (under reasonable assumptions), and this carries over to your problem. Your problem could be much harder.


Preventing multiple threads from racing on a queue while not wastefully polling its size

You wouldn't have just your queue and your semaphore. You would also have a global atomic variable where "false" means "I can guarantee one hundred percent that there is no data in the queue", and "true" means "There is probably some data in the queue, but maybe not".

Any code that modifies the queue would very carefully update the global variable. You need an operating system that makes it possible that code using locking can change such a variable as you need it.

For some interesting reading, google for "dispatch_once implementation".


How is this the expected number of of probes in open-address hashing?

It is the definition of expectation. When the probability of success in exactly $i$ probes is $p(i)$, it means you've been unsuccessful $i-1$ times before! Hence, the expected of unsuccessful steps is $$\sum_{i = 1}^{\infty}(i-1)\times p(i) = \sum_{i = 1}^{\infty}i\times p(i) + \sum_{i = 1}^{\infty}p(i) = 1 +\sum_{i = 1}^{\infty}i\times p(i)\,.$$


Regular expression generating the language $L=\{w: |w|\le 5\}$

If you are allowed to use $\epsilon$, then you can represent "0, 1, or nothing" using $0+1+\epsilon$, and using this it is easy to come up with a short regular expression.

If you are not allowed to use $\epsilon$, then you can use the fact that $L = \bigcup_{i=0}^5 \{ w : |w|=i \}$ to come up with a fairly short regular expression, though I don't know how you would match the empty string.


Here's what I'd use:

partial valuation
value
"partial evaluation" means something different; for instance, if you have the expression (3+x)*y and you learn that x=5, transforming it to 8*y would be an instance of partial evaluation.  Partial evaluation is a technique; it is not a special kind of a valuation.


To which character or characters does a Kleene star apply?

Kleene stars applies to the character(s) it belongs, so in your example the correct option is the 2° one.

ABB* = {AB, ABB, ABBB, ABBBB, ..}

A(BB)* = {A, ABB, ABBBB, ABBBBBB, ..}


If the parent in a bridge is the root, is it a bridge cut node?

By definition, a graph that has only one vertex is connected.

That's to say if you delete A, the graph B is still connected. Clearly, A is not a cut-node because it can't disconnect the graph. So is vertex B.

A vertex is a parent/bridge cut-node if and only if it is not root vertex.

The concepts of these three types of cut-node are introduced by Skiena's in his own book, so these concepts are not very rigorous. An errata list may be a good supplement.


Notation for average case complexity of an algorithm

The notation $\Theta(f(n))$ isn't reserved for worst-case complexity, it's asymptotic notation applicable to functions in general. So you can state that the average case complexity is $\Theta(2.17^n)$, and it means exactly what you think it does. (Regardless of whether this has been proved or not.)


Understanding Incentive Compatibility of pooled Bitcoin Mining paper

Let's assume $n=3$ and at round $t$, miner_1 reported 2 shares, miner_2 reported 3 shares, and miner_3 reported 5 shares. And we'll further assume that in rounds from 0 to $t-1$, none of them reported any shares.

$R$ is the reward function that takes the history of the shares reported by all miners and returns a n-length vector, $a$, consisting of real numbers between 0 and 1.
Where $a_i$ corresponds to the fraction of total reward earned by miner $i$. So $ \sum_i a_i =1 $. $R_i$ corresponds to the reward earned by $i^{th}$ miner. So $R$ returns $<.2, .3, .5>$. When $i=1$, $R_i$ returns $.2$

$b_i$ (normal font) is the total number of shares reported by miner $i$. And $\textbf{b}$ (bold font) is a vector of length $n$, where each element corresponds to the shares reported by each miner. So $\textbf{b} = <2, 3, 5>$. When $i=1$, $b_i = 2$. And vector at round $t$, vector $\textbf{b}$ is denoted as $\textbf{b}_t$. So $\textbf{b}_1$ corresponds to the vector of shares reported at round 1 and $b_1$ corresponds to the shares computed by miner $i$.

Say at round $t+1$, $\textbf{b} = <1, 2, 7>$. So total shares reported in round $t$ and $t+1$ is component wise sum of $\textbf{b}_t$ and $\textbf{b}_{t+1}$.

Hope this helps.


You might be interested in the Universal Algebra point of view of Constraint Satisfaction Problems; see for example this survey by Libor Barto. One classical result in this area is Schaefer's dichotomy theorem.


Are there techniques to know how many times loops like these will run?

If you approximate this as an integral of the second for loop you get, substituting $k=(n-i)$:

$$I_n = \int_1^n \frac{n+(n-k)^2-(n-k)+1}{k} dk = \int_1^n 1+\frac{(n-k)^2+1}{k} dk$$

according to WA, the corresponding antiderivative is of the indefinite integral is:

$$(n^2+1)log(k) + \frac{1}{2}k(k-4n+2) +C$$

Thus, evaluating at $k=1$ and $n$ we get:

$$I_n = (n^2+1)log(n)+\frac{-3+6n-3n^2}{2}$$

So, the discrete sum should approximately reflex that. I graphed it out on desmos, and it seems to show that the exact error grows infinitely, they are asymptotically equal.


This is roughly an open problem subject to ongoing research with various different strategies and heuristics known. A key word is "neural network architecture". The most basic strategy is to iterate through various network topologies and retrain for each one. Another strategy is to start with a relatively larger network and prune connections that have low weight and retrain and look for improvements; years ago this was called "brain damage" in at least one paper [2]. Here are some example references. There are many others. There is also a possibility of using GA-like algorithms to determine the network structure [3]. Here is part of the abstract from [1]:

  The use of ANNs requires some critical decisions on the part of the user, which may affect the accuracy of the resulting classification. In this study, determination of the optimum network structure, which is one of the most important attributes of a network, is investigated. The structure of the network has a direct effect on training time and classification accuracy. Although there is some discussion in the literature of the impact of network structure on the performance of the network, there is no certain method or approach to determine the best structure. Investigations of the relationship between the network structure and the accuracy of the classification are reported here, using a MATLAB tool-kit to take the advantage of scientific visualisation.

[1] Determining Optimum Structure for Artificial Neural Networks by Taskin Kavzoglu

[2] Optimal brain damage Le Cun, Denker, Solla

[3] Finding Optimal Neural Network Architecture Using Genetic Algorithms Britos et al


Just take $k=1$ and use the time hierarchy theorem.


Essentially, anything you can prove for $O(-)$ has a closely related fact that you can prove for $\Omega(-)$, in essentially the same way.  By "closely related", I mean that you might have to swap $\geq$ and $\leq$ and things like that.

You can check that the following is a counterexample to your statement about $a$, $b$ and $c$.
\begin{align*}
    a(x) &= \begin{cases}x&\text{if $x$ is even}\\0&\text{if $x$ is odd}\end{cases}\\
    b(x) &= \begin{cases}0&\text{if $x$ is even}\\x&\text{if $x$ is odd}\end{cases}\\
    c(x) &= x\,.
\end{align*}


Simple algorithm to select separated points in closed intervals

First note that in any optimal solution we can always have $x_1 = a_1$ as we wish to maximize distances, and $x_1 = a_1$ unconditionally does that without sacrificing distance anywhere.

Secondly note that while our 'smallest differences' metric we want to optimize appears a global problem, it really is not if we also sort our $x$. We can have the equivalent definition:

$$\Delta = \min_{1 \leq i < K} \left( x_{i+1} - x_i \right)$$

Now suppose our candidate solution has value $\Delta$. Then given $x_i$ we can find the leftmost $x_{i+1}$:

$$x_{i+1} = \min_y \{ y \mid y \in S \wedge y \geq x_i + \Delta\} $$

So we find $x_1, x_2, \dots$ until we are done. Repeatedly finding which interval in $S$ (if any) will contain $x_{i+1}$ can be done in a combined $O(K)$ time during this process if you just keep track of the highest used interval so far. If there is no valid interval for $x_{i+1}$, it means $\Delta$ is not a valid outcome, but if we find al values up until $x_K$ it is.

So now we have a $O(K + N)$ time test to see whether a certain $\Delta$ is valid. But we can say with certainty that $\Delta \in [0, b_K - a_1]$. So we can do a binary search on this interval using our test to find a range which contains our optimal $\Delta$.

Since each step in this binary search halves the size of the interval that contains the optimal result, we can find optimal $\Delta$ (and corresponding $x_i$) up to a precision of $2^{-p}(b_K - a_1)$ in $O(p(K+ N))$ time.

If you're a bit smarter you can terminate early and exactly as an optimal solution will always contain a limiting sequence of steps of the minimum distance $\Delta$ starting at the left part of an interval and ending at the right part of an interval. Thus we have $a_i + k\cdot \Delta = b_j$. In other words, if our remaining interval contains only a single value of the form $\frac{b_j - a_i}{k}$ for some $i \leq j$ and $k$, then that is the optimal value and you can terminate the search.


Why does a DFA either contain all or no words $a^k$ if it loops for $a$ in all states?

Hint: Suppose that $a^k \in L(A)$ for some integer $k$. Consider the initial state $s$ of $A$. From the premises it follows that $\delta(s,a^k) = s$, and since $a^k \in L(A)$, $s$ must be an accepting state. For every integer $\ell$ we have $\delta(s,a^\ell) = s$ and so $a^\ell \in L(A)$.


What is a "trap" in the context of system virtualization?

A trap is basically a localized exception/fault which occurs when the guest OS does not have the required privileges to run a particular instruction. Operating systems running on top of a virtual machine monitor (a hypervisor) do not know that they are running in the 'user' mode i.e. they can only execute a limited set of instructions, since they do not have full control over the bare-metal. So, when the operating system executes some privileged instructions (instructions which can only be run in the 'kernel' mode or some privileged mode), those instructions create a trap that goes into the hypervisor which then emulates the expected functionality of the OS. Note: that the hypervisor runs the commands and emulates it to the application in a VM, so that the application never knows that it is running in a VM.

Source: https://stonefly.com/blog/deep-dive-virtualization


Prove that every two vertices in graph are connected by a path of some length

$O(n/3)$ doesn't mean what you think it means: in particular, $O(n/3)$ denotes exactly the same class of functions as $O(n)$. However, it's not true that the longest distance between two vertices in a $3$-regular graph is roughly $n/3$. Consider the graph

o---o       o       o             o       o---o
|\ / \     /|\     /|\           /|\     / \ /|
| X   o---o | o---o | o-- ... --o | o---o   X |
|/ \ /     \|/     \|/           \|/     \ / \|
o---o       o       o             o       o---o

(where the Xs denote two crossing edges).  The distance from the top-left vertex to the top-right vertex is approximately $3n/4$.


Recall a few definitions. A language $L \subseteq \{0,1\}^*$ is polynomial-time reducible to a language $L' \subseteq \{0,1\}^*$, often denoted as $L \leq_p L'$, if there is a polynomial-time computable function $f : \{0,1\}^* \to \{0,1\}^*$ such that for every $x \in \{0,1\}^*$, $x \in L$ iff $f(x) \in L'$. Now, $L'$ is $\text{NP}$-hard if $L \leq_p L'$ for every $L \in \text{NP}$. $L'$ is $\text{NP}$-complete if $L'$ is $\text{NP}$-hard and $L' \in \text{NP}$.

It is easy to see that if $L$ is $\text{NP}$-hard and $L \in \text{P}$, then $\text{P} = \text{NP}$. Likewise, if $L$ is $\text{NP}$-complete, then $L \in \text{P}$ iff $\text{P} = \text{NP}$. The intuitive reason is that if $f$ and $g$ are functions that grow at most as $n^c$ and $n^d$ respectively, then the composition $f(g(n))$ grows at most $n^{cd}$, which is also polynomial.

Assume you found a polynomial-time algorithm $A$ for a $\text{NP}$-complete problem $X$. Now, you could in polynomial time transform another $\text{NP}$-complete problem to $X$ and solve it using $A$. This is why we often say that it suffices to study whether any $\text{NP}$-complete problem can be decided in polynomial time.


Status questionis for whether a machine can or can't "think"

EWD898 might be an intersting starting point.

  The Fathers of the field had been pretty confusing: John von Neumann speculated about computers and the human brain in analogies sufficiently wild to be worthy of a medieval thinker and Alan M. Turing thought about criteria to settle the question of whether Machines Can Think, a question of which we now know that it is about as relevant as the question of whether Submarines Can Swim.


Data structure for or-lookups over bit-field associations maps

Preprocessing: For each $(k_i, v_i)$ pair, and for each $x \in k_i$, add $(x, (k_i, v_i))$ to a map data structure (e.g., a hashtable) with $x$ as the key.
To process a query $q$, for each $y \in q$ look up all values in the map, append all of them to a list, and finally remove duplicates (or instead add them directly to a data structure that can collapse duplicates immediately, like a hashtable).


Assuming that P=NP - Finding an optimal algorithm for 3SAT

The following language is in NP (why?):
$$
\{ (\phi,k) : \text{$\phi$ is a CNF and there is an assignment satisfying at least $k$ clauses of $\phi$} \}.
$$
I’ll let you finish the proof.


Should activation function be monotonic in neural networks?

During the training phase, backpropagation informs each neuron how much it should influence each neuron in the next layer.  If the activation function isn't monotonic then increasing the neuron's weight might cause it to have less influence, the opposite of what was intended.  The result would be choatic behavior during training, with the network unlikely to converge to a state that yields an accurate classifier.


What is your approach to unveil the boundary cases when designing an algorithm?

A good answer for this is over at Software Engineering https://softwareengineering.stackexchange.com/questions/72761/how-do-you-identify-edge-cases-on-algorithms

In general look at zero, empty string, max values, odd/even, nulls, sorted/random data where applicable including repeated testing with random data.

Also "think of everything that can go wrong" https://www.quora.com/How-do-you-identify-edge-cases-on-algorithms.


Well, x86 hasn't the simplest instruction format... And similar addressing modes can be named differently for different CPUs.
In most CPUs (particularly RISCs and simple 8bits CPUs), there is only zero or one memory operation for data, so each instruction can be binned in one addressing mode or another.
For CISC CPUs it can be a bit more complex, for example x86 supports writing an immediate value to memory without going through a register.
Intel manuals don't really name the addressing mode for each instruction, because it's too complex, there are instead acronyms to describe operands such as imm8,imm16,r/m8,r/m16...
So your "MOV AH,0x09h" is probably "immediate" addressing, Intel describes it as "MOV r8,imm8" : 8bit register as destination to 8bit immediate.


Examples of infinite sets of regular and non-regular languages that their union is regular and non-regular

a. is pretty easy. Just consider $\{a\}^\ast = \bigcup_{i \in \mathbb{N}_0} \{a\}^i$. This also answers the last question in your post (i.e., regular does not mean finite).

The answer to b., as you have said, can be found in the linked question.

Finally, for c. and d. you can use subsets of $\{ 0^n 1^n \mid n \in \mathbb{N}_0 \}$ and $\{ 1^n 0^n \mid n \in \mathbb{N}_0 \}$, which are both non-regular languages. Hint: The exercise text does not require the languages to be disjoint.


Given the "programs as proofs" isomorphism, how do we know that the program isn't lying?

Proving the correctness of a program in a form of a proof that's nothing but the program itself

This is not quite how the Curry-Howard-Correspondence works.

First one has to show that the language of choice actually corresponds to some consistent logic. Different languages correspond to different logics, and many languages correspond to inconsistent logics which are not good for proving things. Haskell doesn't correspond to a consistent logic, because in Haskell, we can write nonterminating programs which would correspond to infinite proofs. But infinite proofs are invalid, so not every Haskell program corresponds to a valid proof.

Now what does it mean that a language corresponds to a logic? It means that:

a type in the language corresponds to a formula in the logic
a program in the language corresponds to a description of a proof in the logic
a well-typed program in the language corresponds to a description of a valid proof in the logic.
a program of a specific type in the language corresponds to a proof of a specific formula in the logic
a value in the language correspond to truth in the logic
evaluation of programs to values corresponds to soundness of the proving rules
reification of values to programs corresponds to completeness of the proving rules
...

No need to understand all aspects of the correspondence at once, but it is good to keep in mind that the correspondence relates not just programs and proofs, but many (all?) aspects of the languages and the logic. For the question here, only the first four aspects are relevant.

A minor issue is that only well-typed programs correspond to valid proofs. That's why type signatures of functions are so relevant to the Curry-Howard-Correspondence.

The key issue is that a well-typed program doesn't correspond to a valid proof of its own correctness, but to a valid proof of whatever formula corresponds to the program's type.

For example, let us consider the following two programs (using Haskell syntax, but assuming a version of Haskell that corresponds to a consistent logic):

f :: a -> a -> a
f x y = x

g :: a -> a -> a
g x y = y

The functions f and g are well-typed programs of the same type, so they correspond to valid proofs of the same formula. The formula is "forall propositions p, p implies that p implies p".

But clearly, f and g are different programs. And of course, they correspond to different proofs of the same formula. The program f corresponds to the proof "We know that p implies p, so also p implies (whatever implies p)". And the program g corresponds to the proof "We know that p implies p, so also whatever implies (p implies p)."

Usually, with programming languages, we care about the difference between programs like f and g, and with logics, we don't care about the difference between the two proofs that correspond to f and g. But when thinking about the Curry-Howard-Correspondence, it is important not to forget that there can be multiple different valid proofs of the same formula.

  So how do we know that the program is computationally doing the "right" thing (dynamically speaking) and not just faking it to get past a proofing system?

We don't. We only know that the program proves the formula we have encoded in the program's type. So how can we use the Curry-Howard-Correspondence to prove a program correct? We have to encode a statement about program correctness into the type of the program. This requires a very expressive type system, of course, which is exactly what the languages inside tools like Coq or Agda provide.


An earlier proof that associates to an arbitrary graph G a certain "structural graph" was shown by Dinitz, Karzanov and Lomonosov in 1976 [1].

[1] Dinitz, E. A., Karzanov, A. V., & Lomonosov, M. V. (1976). On the structure of the system of minimum edge cuts in a graph. Issledovaniya po Diskretnoi Optimizatsii, 290-306.


What is the expected number of nodes at depth d of a tree after i random insertions

Let $X_{d,t}$ denote the expected number of nodes at level $d$ and time $t$, and let $p_{d,t}$ be the probability that at time $t$, a node is added at level $d$. Our indexing is such that $p_{0,0} = X_{0,t} = 1$. Clearly
$$ X_{d,t} = \sum_{s=0}^t p_{d,t}. $$
Suppose that at time $t-1$, the number of leaves at depth $d-1$ is $X$. Then the probability that at time $t$ a leaf is added at depth $d$ is $X/t$. The expectation of this across the first $t-1$ steps is exactly $X_{d-1,t-1}$, and so
$$ p_{d,t} = \frac{X_{d-1,t-1}}{t}. $$
Therefore
$$ X_{d,t} = \sum_{s=1}^t \frac{X_{d-1,s-1}}{s}. $$
What does this look like? Let's use generating functions:
$$ P_d(z) = \sum_{t=0}^\infty X_{d,t} z^t = \sum_{t=0}^\infty \sum_{s=1}^t \frac{X_{d-1,s-1}}{s} z^t = \sum_{s=1}^\infty \frac{X_{d-1,s-1}}{s} \sum_{t=s}^\infty z^t = \sum_{s=1}^\infty \frac{X_{d-1,s-1}}{s} \frac{z^s}{1-z}. $$
Notice that
$$
\int_0^z P_{d-1}(w) dw = \sum_{s=1}^\infty X_{d-1,s-1} \int_0^z w^{s-1} dw = \sum_{s=1}^\infty X_{d-1,s-1} \frac{w^s}{s}.
$$
Therefore
$$
P_d(z) = \frac{1}{1-z} \int_0^z P_{d-1}(w) dw, \quad P_0(z) = \frac{1}{1-z}.
$$
We can calculate
$$
\begin{align*}
P_0(z) &= \frac{1}{1-z} \\
P_1(z) &= \frac{-\log (1-z)}{1-z} \\
P_2(z) &= \frac{1}{2} \frac{\log^2(1-z)}{1-z} \\
P_3(z) &= \frac{1}{6} \frac{-\log^3(1-z)}{1-z}
\end{align*}
$$
A pattern becomes apparent, and is easy to prove by induction:
$$ P_d(z) = \frac{1}{d!} \frac{\log^d (1-z)^{-1}}{1-z}. $$
We can pack all this data into a bivariate generating function:
$$ P(z,w) = \sum_{d \geq 0} X_{d,t} z^t w^d = \frac{\exp (w\log (1-z)^{-1})}{1-z} = (1-z)^{-w-1}.$$
In principle, we can compute $X_{d,t}$ asymptotically from the generating functions; but it is easier to do this directly:
$$
\begin{align*}
X_{0,t} &= 1 \\
X_{1,t} &= \sum_{s=1}^t \frac{1}{s} = \log t + O(1) \\
X_{2,t} &= \sum_{s=1}^t \frac{\log s + O(1)}{s} = \int_1^t \frac{\log s + O(1)}{s} ds + O\left(\frac{\log t}{t}\right) = \frac{\log^2 t}{2} + O(\log t) \\
X_{3,t} &= \sum_{s=1}^t \frac{\log^2 s + O(\log s)}{2s} = \int_1^t \frac{\log^2 s + O(\log s)}{2s} ds + O\left(\frac{\log^2 t}{t}\right) = \frac{\log^3 t}{6} + O(\log^2 t)
\end{align*}
$$
Generalizing, we get
$$X_{d,t} = \frac{1}{d!} \log^d t + O(\log^{d-1} t).$$
With more work, it is possible to obtain lower order terms as well, indeed a polynomial in $\log t$ followed by a Laurent series.


Proving monad laws for flatMap and unit, given laws for compose and unit

That rule you are asking for is (with slight tweaking) a naturality condition mathematically. It would be more naturally written as: $$\mathtt{compose}(f\circ g,h)=\mathtt{compose}(f,h)\circ g$$
If compose used the typical order for composition, you could write it more prettily as: $$(h\odot f)\circ g = h\odot(f\circ g)$$
where $h\odot f = \mathtt{compose}(f,h)$.

The type A => M[B] corresponds to the hom-functor for the Kleisli category of $M$, $\mathcal{C}_M(A,B)\equiv\mathcal{C}(A,MB)$. Given a Kleisli arrow $h : B \to MC$, we have the function $h\odot- : \mathcal{C}(A,MB)\to\mathcal{C}(A,MC)$, and this is natural in $A$. The naturality diagram is:
$$\require{AMScd}
\begin{CD}
\mathcal{C}(A,MB)@>h\odot ->>\mathcal{C}(A,MC) \\
@V-\circ gVV @VV-\circ gV \\
\mathcal{C}(X,MB) @>>h\odot -> \mathcal{C}(X,MC)
\end{CD}$$
where $g : X \to A$. (In fact, this can also be read as a naturality diagram for $-\circ g : \mathcal{C}_M(A,-)\to\mathcal{C}_M(X,-)$.) That $h\odot -$ is natural can be easily derived from its definition as $f\mapsto \mu\circ Mh \circ f$ where $\mu$ is the multiplication of the monad $M$, i.e. flatten, and $Mf$ is the functorial action of $M$, i.e. map.

At any rate, the equation you want would be a free theorem if Scala was a suitably nicely behaved language. Indeed, that Scala isn't "suitably nicely behaved" is an omnipresent problem and leads to many of these laws not actually holding. (This problem occurs with Haskell too, but not nearly so catastrophically.) I assume Paul and Runar discuss this and free theorems somewhere in the book. They're certainly aware of it.


How does reduction of a decision problem work?

Let $I$ be your instance and consider the instance $I'$ obtained by replacing each bit vector $y$ in $L_1$ with $y' = y \oplus S$ (where $\oplus$ denotes bitwise xor). Call $L'_1$ the list containing all vectors $y'$.
Consider the tuples $(x_1, x_2, \dots, x_l)$ and $(x'_1, x_2, \dots, x_l)$ where $x_i \in L_i$ and $x'_1 \in L'_1$.
We have:
$$
      x_1 \oplus ( \oplus_{i=2}^l x_i ) = \oplus_{i=1}^l x_i  = S \iff  (x_1 \oplus S) \oplus  ( \oplus_{i=2}^l x_i ) = x'_1\oplus  ( \oplus_{i=2}^l x_i ) = S \oplus S = 0,
$$
showing that there is a solution to $I$ iff there is a solution to $I'$ (and you can convert one solution into the other in linear time).


NP hardness of partitioning a graph into two subgraphs

I think you can in fact do this by showing a reduction from the Partition problem, as stated by Chapichap. Recall the direction of reduction that is needed to show a problem is NP-Hard. In general, it is okay if the problem you have is harder than the problem you are using to show hardness (in this case, the partition problem). This is because the reduction would from the partition problem to the given problem. For the partition problem, if we are given a set of numbers $S$, and we want to find a partition $S_1,S_2=S\setminus S_1$, we need to show how to construct a graph $G$ and a number $W$ such that the vertices of $G$ can be partitioned as described (where the sum of weights of the vertices is at least $W$) if and only if the set $S$ can be partitioned.

Consider the following reduction: Let $G = (V,E)$ be a graph where $V=S$. That is, for each number in $S$, create a vertex in $G$. The edge set seems irrelevant here, so we can let $E=\varnothing$. The weight of each vertex is equivalent to the number in $S$ to which it corresponds. Finally, let $\lceil W=(\sum_{x\in S} x)/2\rceil$. That is, $W$ is the sum of the weights of all the elements of $S$, divided by two.

Asking for a partition in $G$ such that each partition has total weight at least $W$ means asking for each partition to contain half of the total weight of the graph. To be thorough, consider the case where $\sum_{x\in S}$ is even. Then $W$ is exactly half of the total weight of all vertices in the graph, and so for each partition to have a total weight of at least $W$, each partition must have equal weight. Thus such a partition of the vertices is equivalent to an equal-sum partition of the elements of the original set. Now, consider the case where $\sum_{x\in S}$ is odd. In such a case, $S$ has no partition such that the sum of the partitions are equal. However, the way we constructed $W$ ensures that $2W = (\sum_{x\in S})+1$ and so it is impossible to partition the graph so that each partition has total weight at least $W$ (the existence of such a partition would imply that the total weight of the graph is strictly greater than $\sum_{x\in S}$, which is impossible).

Hopefully you can see from the above that $G$ has a partition into two subgraphs such that the sum of the weights of vertices in each partition is at least $W$ if and only if the original set $S$ had a partition of its elements into two subsets such that the sums of elements in each subset are equal.


The time hierarchy theorem states that if $f(n)$ is a reasonable function (technically, time-constructible), then there are some languages computable in time $f(n)$ that require (almost) time $f(n)$. More accurately, for any $g(n)$ satisfying $$ \frac{g(n)\log f(n)}{f(n)} \longrightarrow 0, $$
there is a function computable in time $f(n)$ but not in time $g(n)$.

Intuitively, this is saying that if we have more time ($f(n)$ rather than $g(n)$), then we can compute more languages. The theorem is a time-bounded version of the undecidability of the halting problem, and is proved in a very similar way.

In your case, you want to show that time $O(2^{n^\gamma})$ is more powerful than time $O(2^{cn})$. Here is one naive attempt: pick some $f(n) \in O(2^{n^\gamma})$ such that for all $g(n) \in O(2^{cn})$, the prerequisites of the time hierarchy theorem are satisfied. This shows that for each particular $c$, there is a language in EXP not computable in time $O(2^{cn})$. However, for all we know it can be computed in time $O(2^{(c+1)n})$, and so this doesn't show that EXP is larger than E.

Instead, you want to find a single language in EXP which is simultaneously not computable in time $O(2^{cn})$ for all $c$. To ensure that, you need to pick $g(n)$ judiciously, and I'll leave you to that.


Algorithm to sample high-dimensional parameter space of expensive cost function

I don't know how to sample from the space of nearly-optimal solutions, but I'll share one approach you could consider.
It appears that you want to estimate the density of good solutions, at different points in the input space.  It appears you are gridding up the parameter space and estimating the density in each cell of the grid.  Here is a possible alternate method to do that.
Suppose we have a cell $C \subseteq \mathbb{R}^{20}$ in the parameter space, which might take the form $C = [\ell_1,u_1] \times \cdots \times [\ell_{20},u_{20}]$, i.e., $\ell_i$ is the lower bound on the $i$th coordinate and $u_i$ the upper bound.   Let $V(C)$ be the volume of cell $C$.  We'll estimate the density of good solutions in $C$.  Pick a volume $v$ that is a fraction of $V(C)$, let $\alpha=v^{1/20}$, and then repeat the following 100 times:

Pick a random point $w \in C$.  Form the smaller cell $C_x = [w_1-\alpha/2,w_1+\alpha/2] \times \cdots \times [w_{20}-\alpha/2,w_{20}+\alpha/2]$.  Use your optimization method to search whether there is a good solution in the cell $C_x$.  (For many optimization methods, it is easy to enforce constraints that set an upper and lower bound on each coordinate in the parameter space.)

Now based on the number of times that you were able to find a good solution, you can form an estimate of the density of good solutions in $C$.  If this count is close to zero, double $v$ and repeat.  If this count is close to 100, halve $v$ and repeat.  Repeat until you get a count that is not too close to 0 or 100, and the result should give you a pretty good estimate of the density in $C$.
You can now iterate this, once per cell $C$, and use that to produce the kind of plot you are hoping for.
Here I've adopted standard methods for #SAT, i.e., for estimating the number of solutions to a SAT instance, to your specific problem.


Hints...

$L_a$ can be transformed into an well-known non-regular language by a very simple homomorphism that basically "loses" information.

For $L_b$ you might try transforming it into its "opposite" (that is, equality in place of inequality) by operations known to preserve regular languages.  The "opposite" language might then be amenable to a pumping argument. Also, try "testing" your argument on a much simpler version of $L_b$ which, although it is regular, will let you see the patterns to use for the full $L_b$.

PS -- these are both techniques that might be added to the reference post that Dave Clarke points to. I will do so when this question has settled down.

Thinking a bit more about $L_b$, the idea I had in mind to derive the "opposite" language may not lead directly to an easy solution. So here's a hint in a different direction.  There are a lot of $m^{i_j}$ in each string of that language. If you could "isolate" those strings of $m's$ by an appropriate regularity-preserving operation, you might get a simpler language that is amenable to a proof, perhaps by pumping or perhaps by the "opposite" idea.  Also, think about what each $i_j \neq j$ means in terms of other symbols in the string.


how is the set of undecidable programs related to the set of non-halting programs?

The notion of an "undecidable program" doesn't make sense, for the same reasons I gave in response to your last question.  It makes sense to talk about whether a language is decidable or undecidable.  It doesn't make sense to talk about whether a program is decidable or undecidable.  If you check the formal definition of decidable, you'll see that decidability is only defined for languages.

Undecidable is not the same as non-halting.  Check the definition.


Is there a non-recursive and uncountable language L?

Definition: a word over an alphabet $A$ is a finite sequence of elements of $A$.
Definition: a language over an alphabet $A$ is a set of words over $A$.

With these definitions, if $A$ is a finite set, then any language is countable (either finite, or countably infinite). This is because any language is a subset of the complete language $A^*$ (set of words over $A$).

Direct proof sketch: you can enumerate all the words in the language, in order of increasing length (and in lexicographic order for each given length, having defined an order of $A$). This process is well-defined because set of words of a given length is finite. This process assigns an index to all the words in the language because all words have a finite length.

Follow-up exercise: if $A$ is countably infinite then a language over $A$ is countable. Adapt the proof above (change the enumeration order to cover the whole language in finite batches).


Is every problem with an output's size that grows polynomialy np?

No. All problems in $\mathsf{NP}$ are decision problems and, as such, the size of their output is trivially polynomially bounded (the output is just one bit).
Moreover, there are decision problems that are not in $\mathsf{NP}$. Indeed, by time hierarchy theorem $\mathsf{NTIME}(n^k) \subsetneq \mathsf{NTIME}(2^n)$ for every constant $k$.


Restricted Boltzmann machine confusing details

The equation from the wikipedia implemented with this code is the one in picture bellow. Sigma function is logistic sigmoid (self._logistic()). The dot product is the sum of products bellow. bj is offset and might be included in the sum (some visible neuron is always 1) or it might be omitted completely for simplicity or something else.


Why don't we encode church numerals like this?

I think what you really are asking for are criteria for judging correctness of coding. Once you have got these, you can answer your question on your own.

Correctness of coding of some structure always originates from the structure itself. The structure of natural numbers $\mathbb{N}$ is:

A constant $0$,
A unary operation $S$,
For each set $A$, a recursion operator $\mathsf{rec}_A : A \to (\mathbb{N} \to A \to A) \to \mathbb{N} \to A$, subject to equations:
$$\mathsf{rec}_A \; x \; f \; 0 = x$$
and
$$\mathsf{rec}_A \; x \; f \; (S n) = f \; n \; (\mathsf{rec}_A \; x \; f \; n).$$

So whatever your coding of natural numbers is, it has to have $0$, $S$ and $\mathsf{rec}$ (only one will do in the untyped $\lambda$-calculus as there are no types to worry about) such that the above equations are satisfied for all suitable $x$, $f$ and $n$.

You can ask yourself:

  Does your coding allow you write down $0$, $S$ and $\mathsf{rec}$ which satisfy the desired equations?

If it does, then it's a valid coding. There are many codings of natural numbers.


What is a "negative function" withing algorithms?

The big-O notation (and also similar notations, such as big-Omega) are not inherently limited only to describe running time of algorithms. Indeed, when the context is the running time of some algorithm, there are no negative functions since algorithms cannot run "negative time".
That being said, the big-O notation is a general mathematical definition. It could be used for other things as well, as shown in this Wikipedia page.


If all numbers are distinct then you can find the longest path using straightforward dynamic programming. The general problem is probably NP-complete, since deciding whether a grid graph has a Hamilton path is NP-complete, as shown by Itai, Papadimitriou and Szwarcfiter. Grid graphs are finite induced subgraphs of the infinite rectangular grid, in which non-diagonal cells are not adjacent; however it seems reasonable to conjecture that Hamilton path is NP-complete also for finite subgraphs of the infinite rectangular grid with diagonals. Given that, it is likely that your problem is also NP-complete.


How many recursive calls are made by this gcd function?

Hint: on input $F_{n+1},F_n$, gcd makes a recursive call with inputs $F_n,F_{n-1}$. Now use the asymptotic formula $F_n = \phi^n + \Theta(1)$, where $\phi = (1+\sqrt{5})/2 > 1$.

Also, while we're at it, $\Theta(\log_2 n) = \Theta(\log n)$, and similarly $O(\log_2 n) = O(\log n)$ (and the same fore $\log\log n$); try to figure out why (here the base of $\log n$ can be arbitrary, but for definiteness you can choose base $e$).


King of the North: Placing bannermen surrounding castle

This appears to be a max-flow/min-cut problem. Consider the directed graph $G$ with all non-hill/wall squares as vertices and edges between the neighbouring non-hill/wall cells in the map.

As the weights in the problem are on the vertices, but we need them as capacities on the edges, replace each vertex $u$ by the pair of vertices $u_{in}$, $u_{out}$ such that $c(u_{in},u_{out}) = w(u)$ and all incoming edges of $u$ are connected to $u_{in}$ and all outgoing edges of $u$ are connected to $u_{out}$. Give the capacity $+\infty$ to all other edges (so we cannot 'cut' those edges).

Call our castle the sink and connect all borders of the map to a source. Note that the edges can be bidirectional, except for those connected to the source or sink.

Now, the minimum amount of bannermen to required to protect the castle is equal to the minimum value over edges in our graph $G$ we need to remove such that the sink (our castle) cannot be reached from the source (the outside of the map). This is precisely the minimum cut on this graph $G$. So, we can compute the number of men required in $O((R+C)^3)$ using the Edmonds-Karp algorithm, where $R,C$ is the amount of rows and columns in our map. Given that $R,C\leq 300$, this approach is likely fast enough to solve the problem within the time limit.

Your approach looks a lot like an heuristic approach to the min-cut problem. I don't see any reason that this would be always be correct in this case, so that approach would likely fail, as you suspect.


Our problem is NP-complete by a reduction from MAXIMUM BALANCED BICLIQUE PROBLEM (MBBP).

MBBP problem:
Input: A bipartite graph $G(U, V, E)$ and an integer $k$
Output: YES if there exists $A\subseteq U$  and $B\subseteq V$ with $|A|=|B|=k$ and $G[A, B]$ is a biclique, NO otherwise

Given an MBBP instance $G, k$, output the following instance of our problem: $(\bar G, n-k)$ where $\bar G$ is the complement bipartite graph of $G$, namely $\bar G = (U, V, U\times V - E)$.
First, requirement that $|U| = |V|$ in our problem can be easily obtained by adding dummy vertices without harming the hardness of MBBP.
Second, we will show that $(G, k)$ is a YES instance of MBBP iff. $(\bar G, n-k)$ is a YES instance of our problem.
If $(G, k)$ is a YES instance of MBBP, then there exist $A\subseteq U$ and $B\subseteq V$ such that $|A| = k$ and $|B| = k$ and $G[A, B]$ is a biclique. It follows that in $\bar G$ the neighborhood of $A$ is a subset of $V - B$ (all the edges in the biclique are removed). And $|A| = k = n - (n - k)$ and $|V - B| = n - k$. Thus, $(\bar G, n - k)$ is a YES instance of our problem.
Conversely, if $(\bar G, n - k)$ is a YES instance of our problem, then there exist $A\subseteq U$ such that $|\cup_{v\in A}N_{\bar G}(v)| \leq n - k$. By complementing this, we have $|\cap_{v\in A}N_G(v)| \geq k$. So by arbitrarily choose $k$ vertices in $\cap_{v\in A}N_G(v)$ to form $B\subseteq V$. We have shown the existence of a biclique in $G$ satisfying requirement of the original MBBP instance. Hence, $(G, k)$ is a YES instance of MBBP.


Is this formal grammar context-free (CFG) but not context-sensitive (CSG)?

Context-free languages are context-sensitive languages; therefore, if there's a valid CFG for a language, then there is a valid CSG for the same language. Depending on how you define CFGs and CSGs, it's possible that a CFG may not count as a CSG. It's quite often the case that CSGs aren't CFGs, even if the CSG generates a context-free language. Basically, even if CFG does not imply CSG, it is still true that CFL implies CSL. That's the confusion: the Chomsky hierarchy implies things about languages.

If your definition of a CSG says "No ϵ  transitions", you're right. If it says "The only ϵ  transition can be S→ϵ , then you are right. If it doesn't say something specifically excluding α→ϵ , then you're wrong. It's a matter of how you define what consistutes a valid CSG, which sounds obvious, and in fact is.


Why sequential access is faster than random access?

They are talking about two different things.

One is about a medium that supports sequential access versus random access. The other is about reading data that is arranged sequentially or spread out requiring random access for each chunk.

Imagine a deck of cards. If you had it in a stack, and I said to get the 39th card in the stack, you could take cards off the stack one at a time until you got to the 39th card. You need to skip past 38 cards to get to the 39th. Therefore, getting the 39th card is harder than getting the 3rd. This is like a sequential access medium.

Alternatively, let's say you spread out the cards around you in a circle in order. Now it takes just as much time for you to get any card as any other since you just reach in the appropriate direction. This is like a random access medium.

Sticking with the circle, let's say I asked for cards 1, 17, and 42. You can do this pretty quickly, but if I had asked for cards 1, 2, and 3, you could probably do it much more quickly since once you got the first card, you could just scoop up the next two cards all at once. This is the difference between reading sequentially organized data versus randomly organized data. Sequentially reading sequentially organized data is very easy with the stack organization of the deck too once you find the first card.

A seek operation is moving the reading head of the hard drive to a particular location. Once there the hard drive can (very) quickly read a sequential run of data. If all your data is all in a sequential run, then it can be read very quickly once the hard drive seeks to the beginning. If the data is spread all over the hard drive, then it has to seek after each portion, and while it's seeking it's not reading so you are wasting time.

In practice, hard drives (including solid state drives which don't have to "seek") assume that you probably want a bunch of data when you tell it to seek somewhere, so they just read in a bunch of data even if you haven't (yet) asked for it in the hope that you will ask for it in the near future. Other than needing space to store this pre-fetched data, there's no reason not to do this as it's essentially free. The read head is already there. This makes sequentially organized data perform even better and randomly organized data even more wasteful. Similar to this is the fact that there is usually a minimum "block" size of data that you can read and write at a time, and so you are going to get at least a block's worth of data no matter what. Sequentially organized data will fully utilize these blocks (until the last one perhaps). Randomly organized data may or may not depending on whether the "chunks" match some multiple of the block size.


Each finite segment of a noncomputable integer sequence is computable

This is quite a fundamental point in computability theory, which has to do with the difference between being able to find and algorithm and knowing that an algorithm exists.

To illustrate the point, suppose I tell you that I'm thinking of a number between 1 and 10. Is there an algorithm that prints the number I'm thinking of? Of course! for every $i\in \{1,...,10\}$ there is an algorithm that prints $i$ and halts, so in particular, there is an algorithm that prints the number I'm thinkng of.

Do you know which algorithm prints the number I'm thinking of? no.

Similarly, every finite sequence can be printed by some algorithm. If you have a computable representation of that sequence, you can also find that algorithm, but if this finite sequence is given as an uncomputable function, then you cannot find the algorithm.

One classic example for this issue is the following: consider some TM $M$ and input $w$, we define the number $t$ as follows: $t=1$ if $M$ accepts $w$, and $0$ otherwise.

Is there an algorithm that prints $t$? yes - either the algorithm that prints $1$ and halts, or the algorithm that prints $0$ and halts.

Is there an algorithm that, given $M$ and $w$, computes the algorithm that prints $t$? No - as this would contradict the fact that $A_{TM}$ is undecidable.


Which one of the following string is DCFL

Hint: The DCFL among the three alternatives is not only a DCFL, it is a regular language.

(Recall that the regular languages form a subset of the DCFLs.)

Hint no. 2: The other two alternatives are essentially the same language, only over different alphabets.


Does Heapsort work in time o(n log n) in the best case?

The paper: The Analysis of Heapsort by Schaffer and Sedgewick shows that

  Theorem 1: Heapsort requires that at least $\frac{1}{2} n \lg n - O(n)$ data moves for any heap composed of distinct keys.

and that

  Theorem 3: The average number of data moves required to Heapsort a random permutation of $n$ distinct keys is $\sim n \lg n$.

It also mentions that

  If equal keys are allowed, the best case is clearly linear [3]: consider the case of a heap with all keys equal.

The citation to [3] here is TechReport: On Heapsort and its Dependence on Input Data.


$L = \{x\#x^R \mid x\in\{0,1\}^* \} $ not accepted by a queue automaton?

If a queue automaton is Turing-Complete, then it can compute (decide) any function (language) that a Turing machine can. And we know that TM can decide both $L = \{x\#x^R \mid x\in\{0,1\}^* \}$ and $L = \{x\#x \mid x\in\{0,1\}^* \}$, thus both can be decided by a queue-automaton.

"How?" you ask? For this you need to understand how a queue-automaton works. It starts with the input already in the queue (where the end of the input is marked by a special character $\$$), and then at every move it reads the letter at the head of the queue and can insert one or more characters to the end of the queue.

Let $M$ be a TM. The way to simulate $M$ over the queue automaton is to keep reading content out of the queue and then putting it back into the end of the queue. This allows us to make multiple passes over the "tape" of the TM. For instance, assume the queue holds "abc$". A "Cycle" (a pass on the queue) will look like (plotting the queue content):

 abc$ -> bc$a -> c$ab -> $abc -> abc$

and we are back to square one, allowing the machine now to take another pass on the input.

It is then trivial to simulate the TM moves as long the head moves to the right, or stays in place: we can denote the heads place by a special symbol ($\to$) that points on where the TM head looks at. E.g., at the very first move we do:

abc& -> bc$→a -> c&→ab -> ... -> →abc$

Then moving the head to the right is elementary:

→abc& -> abc$ -> bc&a→ -> ... -> a→bc$

It is a bit more tricky to simulate a move of the TM head to the left, because seemingly, we need to put the head even before we see the next letter that causes the move back.

The trick here is to use the current state in order to "keep one letter in the memory". So when we see a letter, we don't immediately put it back to the queue, but we "remember" it using a state (e.g. if the states of the TM are $q_1,q_2,..$ etc, we will move to $q_1^a$ if we see an a or to $q_1^c$ if we see a c, etc.)
Before putting the letter back to the queue we first we check the next letter, and if it is not the head, we put it back, If it is the head, we may move the head as needed.

The cycle of moving the head left will look something like the following:

a→bc$ ->(remember a using states)-> →bc$a -> bc& -> (*)

at this point the machine knows it needs to move the head to the left. It remembers a and so it put it back in the queue, now remembering b using the current state

-> c$→a -> $→ab -> ... -> →abc$


Its hard to say without the knowledge of why a node goes to the left or right of another, and if this carries as a property throughout the tree. If by ambiguously you mean there is more then one valid way of replacing the node and the tree has an ordering structure (such as a binary search tree) then your understanding is correct. The deleted verticie can be replaced with either its in order predecessor, or its in order successor. Both of these will be valid with the ordering property.


Is there a difference between perfect, full and complete tree?

Yes, there is a difference between the three terms and the  difference can be explained as:

Full Binary Tree: A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree.

         18
       /    \
     15      20
    /  \
   40   50
  /  \
 30  50

Complete Binary Tree: A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.

            18
       /         \
     15           30
    /  \         /  \
  40    50     100   40
 /  \   /
8   7  9

Perfect Binary Tree: A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

           18
       /       \
     15         30
    /  \        /  \
  40    50    100   40


Why is ${n \choose 2}$ a $\Theta(n^2)$ computation?

$\Theta$-notation more generally refers to the growth of a function. In terms of computational complexity this function can be done in $O(1)$ as:

$$\frac{n!}{(n-2)!2!} = \frac{n(n-1)}{2!} = \frac{n(n-1)}{2}$$

Since there are a finite number of multiplications and multiplication is sometimes treated as $O(1)$ this has constant computational time. But, the author is not referring to the computational complexity of this function. Instead he is referring to the growth of the function:

$$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2} \in \Theta(n^2)$$


sorting with noisy but persistent answers

For constant $p>0$ there is no way to exactly sort $A$ with high probability. Think, e.g., of the first two elements: they will seem to be in the wrong order with probability $p$ and no other comparison provides any information on their order.

In fact, if an algorithm returns a permutation of $A$ that has maximum dislocation1 $D$ with high probability, then $D = \Omega(\log |A|)$.

The algorithm in the paper by Braverman and Mossel suggested by Yuval returns a permutation with maximum dislocation $O(\log |A|)$ and, in particular, returns the maximum-likelihood permutation. However, its running time can be quite large.

The following papers have improved the time complexity (in chronological order) for the problem of sorting with (asymptotically) optimal $O(\log |A|)$ maximum dislocation. Here the returned permutation does not need to be the maximum-likelihood one and $p$ needs to be smaller than some constant ($1/32$, $1/20$, or $1/16$):

Tolerant algorithms: Lowers the complexity to $O(|A|^2)$.
Sorting with recurrent comparison errors Lowers the complexity to $O(|A|^2)$. The returned permutation also has $O(|A|)$ total dislocation in expectation. This is probably the easiest algorithm to implement.
Optimal Dislocation with Persistent Errors in Subquadratic Time Same dislocation bounds as the above paper but in $\tilde{O}(|A|^{3/2})$ time.
Optimal Sorting with Persistent Comparison Errors. Lowers the complexity to $O(|A| \log |A|)$. The returned permutation has $O(|A|)$ total dislocation, w.h.p.

1 The dislocation of an element in a permutation is the absolute difference between its position and its rank (position in the sorted sequence).


When proving that a problem is NP-hard, we usually reduce another problem, already known to be NP-hard, to out problem. This process must start somewhere - there must be a first problem which is proven to be NP-hard. For this first problem, say SAT, we need to show that every problem in NP can be reduced to SAT. This is the master reduction, which reduces an arbitrary problem in NP to SAT. Following that, we use reductions that reduce a single problem to the problem at hand.

The name master reduction is perhaps common in Germany, but I have never heard of it. In any case it's just an informal name. Just like the fundamental theorem of algebra is some theorem that somebody at some point decided to call that way, so master reduction is just a term that somebody invented for some reason. I have tried to explain the significance of the term above, but in reality there is no higher significance to the term beyond the particular object it refers to.


Knuth's Algorithm X - why do we backtrack rows but not columns?

No, it is not necessary to backtrack the columns.

Take an arbitrary solution $X = \{\text{some row indices}\dots\}$.
In the first step the algorithm picks some column $j$, and in the second step it iterates over all rows $i$ with $A_{ij} = 1$, makes the matrix smaller and recursively calls itself for each such row.

Since $X$ is a valid solution, there exists some $i_0 \in X$ with $A_{i_0 j} = 1$. Let's analyze the iteration step, in which the algorithm chooses the row $i_0$. How does the matrix change?

It removes all columns $k$ with $A_{i_0 k} = 1$: this doesn't bother us. $X / \{i_0\}$ is still a valid solution for the smaller matrix.
It removes all rows, that have at least one set $1$ in a same column as row $i_0$: this still doesn't throw away any important stuff. Because we know that all rows in $X$ have the $1$s in different places. So still all rows of the solution will be part of the smaller matrix.

As you see, it doesn't matter how the algorithm picks the column (any choice of column is possible), you will still find a row, that is part of your solution, the solution is still a solution of the smaller matrix. And by induction, we the algorithm will find the solution. Just the order of the rows of the solutions will differ, if we pick some other column. But we will find the same solutions.


Bin packing variant for maximizing value in a bin

This is the knapsack problem.  It is NP-complete, so there are no algorithms that are both efficient on all problem instances and always optimal, but there are many different techniques that yield different points in the tradeoff between computation time and quality of the solution.


Finding the point with minimum x-ordinate, lying between two y-ordinates

Not unless you assume something more. Without further assumptions, if you don't check all $n$ values, the minimum can be some of the unchecked points.

If you know there is just one minimum in (sorted) range, a variant of binary search (the minimum is the point where $x_{k - 1} > x_k < x_{k + 1}$ or one of the endpoints; if $x_k > x_{k + 1}$ the minimum is to the right, and so on) gets it in time $O(\log n)$.


$2$-sorted array. How to sort it in minimal number of comparisons ?

Hint:Show that the algorithm must compare the following pairs:
$$ (a[1],a[2]), (a[2],a[3]), (a[3],a[4]), \ldots, (a[n-1],a[n]). $$

For each comparison $(a[i],a[i+1])$, assume that you haven't compares $a[i]$ to $a[i+1]$ but you have done all other comparisons. Show that you still don't know the correct sorted order of the array.


Weighted Online Matching - randomized algorithms

A randomized algorithm cannot be constant-competitive in worst-case order.
A proof using Yao's principle can be found here.


Validating a sequence of points as a convex hull

The answer is easier than you think. As you remarked you should check if you take always CCW or CW turns. But of course, this might result in a curve that is self-intersecting. But you can detect this easily, just sum up then angles of the "turns". Since your curve is closed this angle sum is a multiple of $2\pi$. If it winds up exactly once it does not self-intersect. In this case the angle sum is $2\pi$. Thus you are left with checking, if the angles sum up to $2\pi$.

See this paper for analogues in higher dimension.

Interestingly, in the smooth version (CCW turn is here positive sectional curvature), for a 1d curve you still have to check the winding number, but by an old theorem of Hadamard,  if higher dimensional (immersed) manifolds have positive sectional curvature everywhere, then they enclose a convex body.


Sort all coordinates of intervals (annotated with their significance), and scan them in order.

As an example, in your case you would get
$$
1^{+red},5^{+yellow},7^{+green},8^{-green},9^{-yellow},11^{-red},15^{+black},16^{-black}
$$
This immediately gives the decomposition into intervals $$(1,5),(5,7),(7,8),(8,9),(9,11),(11,15),(15,16)$$
with associated colors.

Note that this list differs from your output, since you sometimes move the endpoint back by 1 point for some unspecified reason.


Why we need to read memory on a write-miss?

Because write-miss happens only with just a word  missing in a block. So all of the block which contains that word must be fetched and then that special word must be updated.