Efficiently storing and modifying a reorderable data structure in a database

There are two questions here:

How do you implement a pointer data structure such as a red-black tree in a database?
Should you implement a pointer data structure in your database to solve this problem in practice?

The answer to (1) is easy: add arbitrary IDs to each of your items and use those when you need to store a "pointer" to an item. For example, to implement red-black trees in a typical relational database, you would have a table with one row for each node, with the following columns:

an autoincrement non-nullable integer primary key column, storing the node ID
three nullable integer columns, storing the left, right, and parent node IDs
a non-nullable bit column, storing the red-black flag
columns for whatever actual data is associated with each node

And then you would have a table with one row for each tree, with an integer column pointing to the root node for that tree.
As for (2): if your lists are less than a few thousand elements, it's definitely likely—as @D.W. points out—that the best way to store the ordering in a database is not to do the above. Skip the pointer columns and just give your table of lists a blob column that stores that list's item IDs in order as a series of 2-byte or 4-byte ints. When your app wants to show the list, it reads the entire blob for that list; when it wants to reorder a list, it overwrites that list's blob with an entire new blob. [*]
If your lists are large enough, you might want to start profiling different options' performance. But you mention a drag-and-drop UI, and such UIs are rarely amenable to reordering lists longer than even a few dozen elements.
[*] Implementation note: If you go with this option, make sure you have another column on the items tracking which list each item belongs to, rather than just using a single autoincrement ID column. Otherwise, repeatedly creating and deleting lists could overflow your IDs even if each individual list only has a few items in it!


Perform an operation on an array in O(n)

Yes, you can perform this operation in $O(n)$ using a stack $\mathbb{S}$.

Before presenting the algorithm directly, I would like to give you an illustration using your example. It is not difficult for you to discover the basic idea on your own.

For your example, I give the states of the stack $\mathbb{S}$. Element $P[i]$ and its $S[i]$ are denoted by a pair (P[i], S[i]). The stack reads from left (bottom) to right (top).

Notice which elements are popped before (when) $P[i]$ is pushed and how (and why) $S[i]$ is computed (described as // comments).

initialization: empty
P[0] = 4: (4,1)
P[1] = 3: (4,1), (3,1)
P[2] = 6: (6,3)    // 3 = 1 + 1 + 1
P[3] = 1: (6,3), (1,1)
P[4] = 2: (6,3), (2,2)  // 2 = 1 + 1
P[5] = 7: (7,6)   // 6 = 2 + 3 + 1
P[6] = 9: (9,7)   // 7 = 6 + 1

Here is the basic idea.

Stack $\mathbb{S}$ stores the elements $P[i]$ in array $P$ and its corresponding (already computed) $S[i]$.

Initialization: $\mathbb{S}=\emptyset; \quad \forall i: S[i]=0.$

For each element $P[i]$ in array $P$ in order:

$\textsf{Pop}$ the elements in stack $\mathbb{S}$, until it encounters a bigger one than $P[i]$. This step simulates the "advance toward" procedure. Meanwhile, compute the sum of the $s$ values of all elements that are popped by $P[i]$. Then, $S[i]$ for $P[i]$ equals $1$ plus this sum.
Then $\textsf{Push}$ $P[i]$ and its corresponding value $S[i]$ (just computed) into $\mathbb{S}$.


Saving information from reaching definition

Here are just a few examples:

dead-code elimination,
instruction reordering, and
(implementation of) scoping/shadowing.


What is the complexity of these tree-based algorithms?

Apply the master theorem.

The first algorithm takes $O(N^2)$ time because your underlying recurrence is

\[ T(N) = 2T(N/2) + N^2 \]

The second algorithm takes $N\log^2N$ time as you mention. If your work per node is as indicated (and is tight) then this bound is tight as well.

Update: as commenters point out, the assumption here is that the tree is weight-balanced: each child has half the nodes of the parent. This would imply the log N height bound you indicate, but is not implied by it.


Given a set of LTL formulas, on which states does the Kripke structure hold?

A couple of comments:

Note that "in the future" is not strict, i.e. $Fb$ is also satisfied whenever $b$ itself holds.
Looks fine to me.
Also ok, though I'm not sure if your interpretation would be very enlightening in a more complicated Kripke structure.
"$Xa\Rightarrow Xb$ is true for every state" is a CTL-ism. What you want to say is that for every state along every path, if $a$ holds in this state and $b$ holds in the next state, then $a$ also holds in the next state.Is this the case?
Here you want some finite number (possibly $0$) of $a$s, followed by some finite number (possibly $0$) of $b$s, followed by a $c$. Is this what you see along every path starting in the states you give?


Merge k sorted arrays of exponentially increasing lengths

We can describe any merging algorithm in a tree form (each internal node corresponds to a merged array). Suppose that the cost of merging two arrays $B,C$ is exactly $|B|+|C|$. Then the total cost equals $\sum_{i=1}^k d_i |A_i|$, where $d_i$ is the depth of the leaf $A_i$.

Consider now an arbitrary merge tree $T$. Suppose that $A_k$ is not a child of $T$. In that case, we can form a new tree $T'$ as follows: let $T^-$ be $T$ with $A_k$ removed (and its sibling promoted to its father), and let $T'$ be the tree with children $A_k$ and $T^-$. The cost of $T'$, denoted $C(T')$, satisfies
$$
C(T') = 2^k + C(T^-) + \sum_{i=1}^{k-1} 2^i < 2\cdot 2^k + C(T^-) < C(T).
$$
Here $2^k$ is the cost of $A_k$ and $\sum_{i=1}^{k-1} 2^i$ is the additional cost of all other leaves (since they are all one level deeper).

We conclude that $A_k$ must be merged last. Continuing this way, we see that the optimal schedule merges $A_1,A_2$, merges the result with $A_3$, merges the result with $A_4$, and so on.


How to find indexes of numbers that has many occurrences?

Let's assume for simplicity that $n$ is divisible by $4$. Aiming for a contradiction, suppose that there is some popular number (a number is popular if it appears at least $n/4+1$ times) which does not appear at any of the positions $n/4,n/2,3n/4$. Denote this popular number by $x$.

  Can $x$ appear before position $n/4$? between positions $n/4$ and $n/2$? between positions $n/2$ and $3n/4$? after position $3n/4$?

If the answer to all of these questions is no, then we have reached a contradiction, and the only way out is that $x$ appears in one of the positions $n/4,n/2,3n/4$.


Are self-stabilizing algorithms guaranteed to work in parallel?

I suggest you look for a textbook that provides an introduction to self-stabilizing algorithms (with some definitions, examples, etc.), and work through that textbook.  I think that will provide you a much better understanding, and you'll be able to answer this kind of question yourself.  Trying to learn a subject by reading Wikipedia and asking questions on StackExchange sites is not the way to go.

For instance, I think you'll find that, yes, of course each distributed node is working concurrently (in parallel); that's what it means for a system to be a distributed system.   And yes, for a self-stabilizing algorithm to be correct, one must show that it will never enter an infinite loop of the sort you describe; this is the convergence property.

Designing an algorithm with these properties is non-trivial, but in general, designing self-stabilizing systems is not easy.  No one ever promised this stuff would be easy.


Approximation algorithm question, clustering on n points

There's an even simpler algorithm, the greedy algorithm. This algorithm iterates through the points in some order. Initially the set of centers is empty. When point $p$ is reached, if $p$ is within distance $2\Delta$ of one of the selected centers, then we do nothing. Otherwise, we add $p$ to the set of centers. Naive implementation of this algorithm runs in time $O(kn)$, which is polynomial.

Why does this work? Suppose that balls at radius $\Delta$ centered at the points $p_{i_1},\ldots,p_{i_k}$ cover the entire set, and suppose that the algorithm above has selected points $p_{j_1},\ldots,p_{j_k}$. We have to show that every point in the set is within distance $2\Delta$ of these points.

For a point $p$, let $c(p)$ denote the point among $p_{i_1},\ldots,p_{i_k}$ which is closest to $p$.
I claim that $c(p_{j_a}) \neq c(p_{j_b})$ for $a \neq b$. Indeed, by construction $\|p_{j_a}-p_{j_b}\| > 2\Delta$. But if $c(p_{j_a}) = c(p_{j_b}) = q$, then $\|p_{j_a}-p_{j_b}\| \leq \|p_{j_a}-q\| + \|q-p_{j_b}\| \leq 2\Delta$.

Renumber the points so that $c(p_{j_a}) = p_{i_a}$, and consider an arbitrary point $p$ in the set. Suppose that $c(p) = p_{i_a}$. Then $\|p-p_{j_a}\| \leq \|p-p_{i_a}\| + \|p_{i_a}-p_{j_a}\| \leq 2\Delta$.


Count number of the ways to fill a N-lengthed binary string

Construct a DFA for your language (without the length $N$ restriction). It should contain $S = O(K)$ states. Consider the corresponding $S \times S$ matrix $A$, in which $A(s,t)$ is the number of characters that cause the DFA to move from state $s$ to state $t$. Let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then the number of words of length $N$ is $xA^Ny$. You can compute $A^N$ quickly using matrix exponentiation.


Is there a generic way to parallelize algorithms?

No, there cannot be such a generic method to produce algorithms $A_{in}, A_{out}, A_{1},\dots, A_k$ with the requested properties. The basic problem is that the requested parallel algorithm only uses a single round. (And allowing $A_{in}$ and $A_{out}$ only $O(k)$ time is very restrictive, they cannot even read length-$n$ input or write a length-$n$ output in that time.)

One simple problem which even has a parallel algorithm (but not of the form stated in the question) is the all-prefix-sums operation. Input is a list of numbers, and output is another list, whose elements are the sum of all previous elements in the original list. See section "3.2 Scans" on page 23 in

Parallel Algorithms (64 pages)
https://www.cs.cmu.edu/~guyb/papers/BM04.pdf
by Guy E. Blelloch and Bruce M. Maggs – 1996

There are at least two possible criticisms of this answer. (1) The counter-example problem took a list of size $n$ and output a list of size $n$. Maybe the question expected the output to be much shorter than the input, like in a decision problem. (2) No explicit proof is given that the counter-example problem has no parallel algorithm of the form stated in the question.

Regarding (1), an output of length-$n$ is used to get around Barrington's theorem, as explained in a comment below the question. Regarding (2), one might look at the elements from $n/2$ to $n$ of the output. Each of them would require more than $n/2$ additions, if computed in isolation. $A_{out}$ can only output $O(k)$ of them in $O(k)$ time, so most of them must be computed in partial isolation. Hence, the algorithms $A_i$ outputting them will need more than $O(n/2)$ time.


The language specification defines what the operator does, and the compiler produces the appropriate machine instructions to implement this. In general, there's no reason to assume that the operator is implemented as a sequence of statements in the language that's being compiled (e.g., operators in C aren't first translated into longer expressions in C).

In many cases, (e.g., addition and multiplication), the appropriate machine instructions will be just one instruction.


Example of Minimum Test Collection Problem

The formal definition of the problem from Garey and Johnson is

  Minimum Test Collection

  Instance: A finite set $A$ of "possible diagnoses," a collection $C$ of subsets of $A$, representing binary "tests," and a positive integer $J\leq |C|$.

  Question: Is there a subcollection $C'\subseteq C$ with $|C'|\leq J$ such that, for every pair $a_i,a_j$ of possible diagnoses from $A$, there is some test $c\in C'$ for which $|\{a_i,a_j\}|\cap c|=1$ (that is, a test $c$ that "distinguishes" between $a_i$ and $a_j$)?

Think of $A$ as a set of diseases, and each element of $C$ is a set of all the diseases in $A$ that have some particular symptom.  You can use these sets to figure out what disease a person has. For example (not necessarily medically accurate), suppose our diseases are
$$A = \{\mathrm{flu}, \mathrm{measles}, \mathrm{ebola}\}$$
and our tests are
$$C = \{\mathrm{cough}, \mathrm{rash}, \mathrm{bleeding}\}\,,$$
where
\begin{align*}
\mathrm{cough} &= \{\mathrm{flu}, \mathrm{ebola}\}\\
\mathrm{rash}  &= \{\mathrm{measles}, \mathrm{ebola}\}\\
\mathrm{bleeding} &= \{\mathrm{ebola}\}\,.
\end{align*}

A doctor might try to diagnose a patient by checking whether they have a cough and/or a rash and whether they're bleeding. Minimum Test Collection asks if we can do any better than that, since tests might be expensive to carry out.

In this case, we can.  It's enough to check whether the patient is coughing and whether they're bleeding. If they're bleeding, we know they have ebola. If they're not bleeding, but they are coughing, they have the flu; if they're neither bleeding nor coughing, they must have the measles.  (Note we're assuming as part of our test procedure that these are the only three diseases in the world, and that people only go to the doctor if they have at least one symptom.)


Non-deterministic 2-tape Turing Machine that recognizes palindromes in linear time

Hint. Suppose that, instead, the alphabet was $\{a,b,c\}$ you wanted to recognize

$$\{wcw^{\mathrm{R}}\mid w\in\{a,b\}^+\}\,.$$

How would you do that on a deterministic version of the machine you're trying to use?  Now, in the real problem, nobody's telling you where the middle of the string is.  How would you use nondeterminism to get around that problem?


How do I write a proof using induction on the length of the input string?

As it is unclear where your problem lies, I'll start at the very beginning.

Mathematical induction works like the game of Chinese whispers (in the ideal case, i.e. all communication is lossless) or (perfectly set up) dominoes: you start somewhere and show that your every next step does not break anything, assuming nothing has been broken till then.

More formally, every induction proof consists of three basic elements:

Induction anchor, also base case: you show for small cases¹ that the claim holds.
Induction hypothesis: you assume that the claim holds for a certain subset of the set you want to prove something about.
Inductive step: Using the hypothesis, you show that the claim holds for more elements.

Of course, the step has to be tuned such that it covers the whole base set (in the limit).

Important note: people who are confident of their induction skills often gloss over the anchor and leave the hypothesis implicit. While this is fine when presenting your work to an expert audience (e.g. a paper), this is not recommended when doing proofs yourself, especially as a beginner. Write down everything.

Consider a simple example over $(\mathbb{N},\leq)$; we want to show that $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ holds for all $n \in \mathbb{N}$.

Anchor: For $n=0$, $\sum_{i=0}^{n} i = 0 = \frac{n(n+1)}{2}$ clearly holds.
Hypothesis: Assume that $\sum_{i=0}^{k} i = \frac{k(k+1)}{2}$ holds for an arbitrary, but fixed² $n \in \mathbb{N}$.
Step: For $n+1$, compute the sum:

$\qquad \displaystyle \sum_{i=0}^{n+1} i = (n+1) + \sum_{i=0}^{n} i \overset{\text{IH}}{=} n+1 + \frac{n(n+1)}{2} = \frac{(n+2)(n+1)}{2}$

So the identity holds for $n+1$. (We note that we only needed a tiny part of the hypothesis, namely for $k=n$. That often happens.)

The inductive principle now assures us that the claim indeed holds: we have directly shown it for $0$. The step says, if it holds for $0$, it also holds for $1$; if it holds for $1$, it also holds for $2$; and so on.

Let's have a look at another example, this time on $(2^\mathbb{N}, \subseteq)$. The claim we want to prove is: for every finite subset $A$ of $\mathbb{N}$, the size of the power set $2^A$ of $A$ is $2^{|A|}$³. We perform our induction over $(\mathbb{N}, \leq)$, again, namely over the size of subsets $A$.

Anchor: Consider the (only) set of size $0$, the empty set. Clearly, $2^\emptyset = \{\emptyset\}$ and therefore $|2^\emptyset| = 1 = 2^0$ as claimed.
Hypothesis: Assume that for all sets $A \subseteq \mathbb{N}$ with $|A| \leq n$ with some arbitrary, but fixed $n \in \mathbb{N}$, we have $|2^A| = 2^{|A|}$.
Step: Let $B \subseteq \mathbb{N}$ arbitrary⁴ of size $n+1$, and let $b \in B$ arbitrary (such $b$ exists as $n+1 > 0$). Now the hypothesis applies to $B \setminus \{b\}$ and thus $|2^{B \setminus \{b\}}| = 2^n$. Since

$\qquad \displaystyle 2^B = 2^{B \setminus \{b\}} \cup \{ A \cup \{b\}\mid A \in 2^{B \setminus \{b\}} \}$,

we have indeed that $|2^{B}| = 2 \cdot |2^{B \setminus \{b\}}| = 2 \cdot 2^n = 2^{n+1}$ as claimed.

Again, by induction the claim is proven.

Now, for your problem can use a common trick: strengthening the statement. If you formulate your claim as "the automaton accepts all words with an odd number of ones", you get an induction hypothesis like "among all words of length $n$, exactly those with an odd number of ones are accepted by the automaton". This won't lead you anywhere since we don't know anything about how many ones are contained in which part of a given (accepted) word; the hypothesis does not apply on whatever you cut away of your arbitrarily selected word.

Therefore, you want to formulate a stronger claim: "The automaton is in state $B$ if and only if the consumed part of the input contained an odd number of ones", and show this one. Note that it implies the former claim.

Anchor: After processing the only string of length zero, $\varepsilon$, the automaton is clearly in state $A$ as claimed.
Hypothesis: Assume that claim holds for input fragments of length up to $n$ which is chosen arbitrarily, but fixed.
Step: Consider an arbitrary word $w \in \{0,1\}^{n+1}$. There are two cases.

$w$ contains an even number of ones. There are two cases for the last symbol.

$w_n = 0$: In this case, $w' = w_1 \dots w_{n-1}$ contains an even number of ones. By induction hypothesis, the automaton is in state $A$ after consuming $w'$. Consuming $w_n = 0$ causes the automaton to stay in state $A$, as claimed.
$w_n = 1$: In this case, $w' = w_1 \dots w_{n-1}$ contains an odd number of ones. By induction hypothesis, the automaton is in state $B$ after consuming $w'$. Consuming $w_n = 1$ causes the automaton to switch to state $A$, as claimed.

$w$ contains an odd number of ones. Similar to case 1.

The principle of induction implies that the claim indeed holds.

You perform induction along some partial order; the anchor needs to cover all minimal elements, and sometimes more (depending on the statement).
The "arbitrary, but fixed" is essential! We can not change $n$ in the step and treat it as if it were a fixed number, but we can also not assume anything about it.
Denoting the power set with $2^A$ may seem weird. It is rooted in the observation that the power set is equivalent to the set of all functions from $A$ to ${0,1}$, which is denoted thus.
Choosing $B$ arbitrary is essential for covering the whole space. One may be tempted to say, "Take any such $A$ and add an element that was not there before.". In this case, that would do the same, but it can be easy to get wrong in more complicated settings (e.g. adding nodes to graphs). Always take an arbitrary larger object and then cut it apart to apply the hypothesis on its parts; never assemble the larger object from smaller which are covere by the hypothesis.


I think the author is just saying the circular list has capacity of $n-1$ where $n$ is the total cells. When the array is doubled there is copying of these $n-1$ elements to new array in addition with shifting of these $n-1$ elements in the worst case, thus making it total $2n-2$ doubling and sliding in the worst case.


What are some complexity classes for neural networks?

Basically, no one has proven anything useful about which tasks a neural networks are able to efficiently learn to solve.

What we can say is: they're not magic pixie dust.  They can't solve NP-complete problems in polynomial time, unless P = NP.

In practice, for most tasks that you'd find in a classical algorithms class, human-made algorithms vastly outperform neural networks.  The situations where neural networks are better tends to be tasks that don't admit a crisp problem statement or specification of the desired behavior.


Looking for algorithm to iterate over matrix

The classical recursive algorithm to calculate the Cartesian product $A_1 \times \cdots \times A_n$ goes as follows:

If $n = 0$, return the empty tuple.
Otherwise, for every $x_1 \in A_1$ and $(x_2,\ldots,x_n) \in A_2 \times \cdots \times A_n$, output $(x_1,x_2,\ldots,x_n)$.

In the second step, you compute $A_2 \times \cdots \times A_n$ recursively.

You can convert this into an iterative algorithm. Suppose that $|A_i| = m_i$, and that the individual elements are $a_{ij}$. We count from $0$ to $m_1 \cdots m_n - 1$, and interpret each of these numbers as a mixed base number, involving the bases $m_1,\ldots,m_n$. We then convert the number into a tuple.

An alternative presentation of the iterative approach uses $n$ counters $c_1,\ldots,c_n$ counting from $0$ to $m_i-1$; when a counter reaches $m_i$, we reset it and all following counters to zero, and update the tuple accordingly.

Details of all these approaches left to you.


Can the Hamiltonian path problem be solved by dynamic programming in $O(2^n n)$ time?

Yes, the problem can be solved in $O^*(1.657^n)$ time using algebraic methods. See the FOCS paper of Björklund [1].

[1] Björklund, Andreas. "Determinant sums for undirected Hamiltonicity." Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on. IEEE, 2010.


I suggested looking at the Reddit ranking system in a comment, however,
that system is made in such a way that the time of creation is what
matters, and that's not really relevant in your scenario.
I therefore suggest a physics-based approach.
Model each app as a balloon (circular, in vacuum).  Every time you open
an app, it corresponds to hitting the balloon straight upwards (like a
volleyball set hit), and when you're not hitting the balloon, it falls
towards the earth.  Once it hits the ground it can remain idle (or bump
up a bit if you want to remind the user of apps they forgot about).
In order for an app to remain "hot" you need to keep it above ground.
So how to implement this?
We have a list of timestamps that maps days since epoch to the number of
times it was opened that day.  In the below sketch, I use a linear decay
(gravity would of course be quadratic).
You need to experiment with the constants and try different functions
(logarithms and polynomials) to get it to work to your likings.
Sketch
USAGE = {  # map day to number of opens for that day
    "A": {0: 2, 1: 2, 2: 2, 3: 2, 4: 2},
    "B": {0: 10, 1: 0, 2: 0, 4: 0},
    "C": {0: 0, 1: 3, 2: 3, 4: 3},
    "D": {0: 0, 1: 0, 2: 0, 3: 5},
    "X": {0: 3, 1: 3, 2: 3, 3: 3, 4: 0},
    "Y": {0: 0, 1: 0, 2: 0, 3: 0, 4: 3},
    "Z": {0: 0, 1: 0, 2: 0, 3: 0, 4: 2},
}
IMPACT = 1.1
DECAY  = 1.1

def rank_app(timemap, t):
    """Return the "height" of the balloon on day t given the timemap"""
    height = 0
    for day in range(t + 1):
        height += timemap.get(day, 0) ** IMPACT  # impact of opening
        since = abs((t - day - 1))
        height = max(0, height - since ** DECAY)  # decay
    return round(height, 1)

def rank(usage, day):
    """Return (heigh, app) for each app on given day t."""
    return sorted(
        [(rank_app(usage[app], day), app) for app in usage],
        reverse=True,
    )

print("\n".join([f"{e[0]} {e[1]}" for e in rank(USAGE, day=5)]))

... which gives
3.9 D
2.6 X
2.6 C
2.3 Y
2.3 A
1.1 Z
0.5 B

Notice that D is on top because it was visited 5 times yesterday.  On
the other hand, B was visited 10 times on Day 0, but hasn't been
visited since, so it is on the bottom.
If you are worried about the space it takes to store all the timestamps,
you can truncate the list at any point and replace with its height at a
given day.


What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$

The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest way to calculate it, and it's true even if the SUHA doesn't hold.

But since you asked, let's look at the distribution of the chain lengths.

Suppose you're putting $n$ pigeons into $m$ pigeonholes at random. Examine one pigeon hole (say, pigeonhole number 1). The number of pigeons that are assigned to this pigeonhole follows a binomial distribution; the probability that there are $k$ pigeons in that particular pigeonhole is ${n \choose k} p^k (1-p)^{n-k}$ where $p = \frac{1}{m}$.

So the expected number of pigeons in that pigeonhole is:

$$\sum_{k=0}^{n} k {n \choose k} p^k (1-p)^{n-k}$$
$$= \sum_{k=0}^{n} np {{n-1} \choose {k-1}} p^{k-1} (1-p)^{n-k}$$
$$= np \sum_{k=0}^{n-1} {{n-1} \choose {k}} p^k (1-p)^{n-1-k}$$
$$= np \left(p + (1-p)\right)^{n-1}$$
$$= \frac{n}{m}$$

By the way, if we want to reason about the number of chains of length $k$ in a hash table, for large enough $m$, it's well-approximated by a Poisson distribution.

The expected proportion of hash slots with chain length $k$ is:

$$\hbox{Pr}(\lambda,k) \approx \frac{e^{-\lambda} \lambda^k}{k!}$$

where $\lambda$ is the load factor. Note that $\lambda$ is also the mean of a Poisson distribution, so once again, the expected value of the chain length is the load factor.

You can learn a lot from this. For example:

If the load factor is 1, the expected proportion of hash chains of length 0 and the expected proportion of hash chains of length 1 are both $\frac{1}{e}$.
If you have a hash table with $m$ slots, there is a 50% chance of a collision after you insert $\sqrt{m}$ items. (Exercise: prove this!)


Is it possible for a Turing machine to be able to reduce a grammar and tell where it fits in chomsky hierarchy?

It is not possible: it is undecidable whether a context-free grammar describes a regular language. For a proof, see e.g. Undecidable Problems for Context-free Grammars by Hendrik-Jan Hoogeboom.


If a language is X-complete, is its complement is X-complete as well?

I was thinking that it has to do with accepting states in Touring Machine. You should just switch them so the complexity should be the same but I'm not sure.

That argument does not always work. You are probably thinking of the proofs that REG and R are closed against complement.
Note how the same technique alread breaks down for CFL; it's not that easy for NPDA (or, in fact, for any non-deterministic automaton model). Also, we know that RE ≠ co-RE so the technique does not even work for all deterministic models.

This leads me to this answer: the flip-final-state technique works for membership in some deterministic classes; I'm not sure if completeness then works out as well, but my gut feeling is yes.

The technique is unlikely to work even for membership in nondeterministic classes. As a matter of fact, we do not know if NP = co-NP and, as a consequence, we do not know if NPC = co-NPC.
And, of course, REC ≠ co-REC.

Another thing to keep in mind is that the notion of completeness depends on the type of reduction you consider. For instance, above mentionen open question about co-NPC and NPC applies only to Karp reductions; under Cook reductions, co-NPC = NPC (see e.g. here).


Create a binary search tree from a sorted array: Space complexity reasoning

I would say try to think about it more in the terms of data structures used directly in the calculation of the result. Typically you wouldn't consider the call stack because you could in theory rewrite you algorithm to be iterative and have no issues with the call stack. The call stack is only an issue when you reach the max recersion depth. It is also not considered when just analyzing algorithms.

Space complexity is constant or $O(1)$ because you can modify the tree in place.

Your answer about call stacks more so relates to the worst-case time complexity as this is directly related to number of function calls (or call stacks in your case). This is going to be $O(\text{height})$ of the tree which is at most $n$, so $O(n)$ in worst case, but $\Theta(\log(n))$ in average case. The time complexity can be improved to better than $O(n)$ if you keep your tree balanced after each insertion.


Your proof doesn't work, since you're using an oracle reduction rather than a many-one reduction.

To show that a problem $A$ is NL-complete, you need to show that for every $S \in \mathsf{L}$ there is a logspace-computable function $f_S$ such that $x \in S$ iff $f_S(x) \in A$ (that's the definition); it's enough to show such a reduction for a single NL-complete problem $S$ (exercise). You show instead that $x \in S$ iff $f_S(x) \notin A$.

Showing that nonSTCON is NL-complete is actually not so easy. Even showing that nonSTCON is in NL is not so easy; it is equivalent to showing that NL equals coNL. This is a non-trivial result due to Immerman and Szelepcsényi.


Triangles covering all vertices of a tri-partite graph

First, let's invent a decision version of your problem, in which a number $t$ is given in addition to the graph, and the goal is to decide whether the vertices in the input graph can be covered with at most $t$ triangles.
If the NP-hard problem 3-dimensional matching (3DM) remains NP-hard under the restriction that $|V|$ is divisible by 3 and the target parameter $k=|V|/3$ (which I consider very likely but don't know for sure), then your problem is also NP-hard by reduction from it:
Given such an instance of 3DM, construct an instance of your problem on the same set of vertices by creating a triangle $abc$ for each 3-tuple $abc$ in the 3DM instance, and setting $t=|V|/3$. Clearly a solution to the 3DM instance corresponds to a solution to the constructed instance of your problem. Such a solution is optimal since all 3-tuples are disjoint. In the reverse direction, if all vertices can be covered using just $|V|/3$ triangles then the triangles must all be disjoint, meaning this corresponds to a valid solution to the original 3DM instance. Together, this means that the answer (YES or NO) is the same to both problem instances. Since the construction is polynomial time, and if the restricted variant of 3DM is NP-hard, so is your problem.
To extend this to a full proof of NP-hardness, one approach would be to try to prove NP-hardness of the restricted variant of 3DM -- e.g., by reducing the general variant to it.


What is an intuitive way to explain and understand De Morgan's Law?

Insert real-world predicates and read aloud, for instance:

  It can not be both winter and summer (at any point in time).

and

  (At any point in time) It is not winter or it is not summer.

Clearly, the two statements are equivalent.


Linear time algorithm for array with distinct element

You cannot do it in linear time using only comparisons. If you could, then you could do it for the array and its reverse in $O(n)$ and then for each element determine in $O(1)$ its position in the sorting of the array. This gives a comparison-based linear time sorting algorithm, which we know cannot exist.

You have to tell us more about the domain of the elements in the input array if you want to get an $o(n \log n)$ algorithm. For example, do you have a constant upper bound on the value of the maximum element?


Randomized Rounding of Solutions to Linear Programs

Of course, if you round, you have to verify that rounding preserves feasibility.

Let us for example consider the relaxed VERTEX-COVER LP formulation.
$$
\begin{array}{lll}
\text{min} & \sum_{v\in V}c(v)x_v & \\
\text{s.t.} &x_u+x_v\ge1, & \quad (u,v)\in E \\
&x_v\ge 0. & \quad v\in V
\end{array}
$$

It is known that the solution to this problem is half-integral, i.e., each variable is either $0$, $1$, or $1/2$. The rounding scheme works as follows, whenever your solution contains $x_v=1/2$ you round up and set $x_v=1$. The constraints of the ILP were
$$
\begin{array}{lll}
 &x_u+x_v\ge1, & \quad (u,v)\in E \\
&x_v \in \{0,1\}. & \quad v\in V
\end{array}
$$
Both constraints are fulfilled after the rounding. And you have a nice 2-approximation.


Why is the word "calculus" used to describe systems of logic and computation?

The word calculus comes from the Latin word for limestone, because limestone pebbles were used for counting; you may have a renal calculus: a kidney stone$^1$.

In mathematics, the word is used to describe any system in which symbolic expressions are manipulated by fixed rules$^1$, so we may speak of tensor calculus, vector calculus, predicate calculus, $\lambda$-calculus and integral and differential calculus$^2$. The latter two are related to the former in the sense that both are sets of rules for manipulating expressions. Running a Google Books ngram search on these words, approximately 1890 was the first year in which both "vector calculus" and "tensor calculus" were mentioned, and they have been in frequent use ever since.$^3$

The reason that to you, these systems seem to be using the wrong meaning of calculus is probably that you grew up associating calculus with differentiating and integrating real-valued functions, but this is a bias.

References

[1] Wiktionary page for Calculus

[2] Wikipedia Disambiguation page for Calculus

[3] Google Books search for integral, differential, vector, tensor calculus


"The order of the row don’t matter, as long as you cover every possible combination of input values. Doing this without an order in mind, does not make it incorrect, but it does make it easier to miss some entries. I think your prof is suggesting using a order so you cover all the combinations in a systemic way. What I do, if I have N Boolean inputs for example, I start with the first row have all values assumed false. In the next row, I make the Nth bool true, then only the N-1  true, then both N and N-1 true, then N-2  true with N and N-1 false, and so on. Any such system is fine."
-@Scottk

"@ScottK Summary: you order the rows to be the binary representation of the numbers $0, \dots, 2^N-1$.
"
-@DavidRicherby

"Your prof seems to be wanting you to follow the binary ordering that @DavidRicherby pointed out earlier: either starting with all true or all false. All orders are correct but go with the binary order since that is what your prof seems to be teaching you, and it is was most pros use. There are other useful orderings that engineers use for circuit simplification for example Karnaugh  Maps https://en.m.wikipedia.org/wiki/Karnaugh_map"
-@Scottk


What's better for an algorithm complexity, O(log n) or amortized O(log n)?

$O(\log n)$ in the worst case implies $O(\lg n)$ amortized.

Basically, given two data structures supporting the same operator, one in $O(\lg n)$ time in the worst case and the other one in $O(\lg n)$ amortized time, the first one is considered to be superior asymptotically: being $O(\lg n)$ time in the worst case means that each call of the operator will be supported in this time, while having an amortized complexity of $O(\lg n)$ means that some (very few) operator calls can take $O(n)$ time. Usually, the concept of amortized analysis is used for data-structures which amortized complexity is better than their worst case complexity.

As an illustration, consider a data-structure for integers, storing each such integer $x$ as a string of bits (e.g. $x=8$ represented by $(1,0,0,0)$), and the operator $x.inc()$ which increments $x$ by $1$.

In the worst case (e.g. on $x=7$ represented by $(1,1,1)$), the operator $x.inc()$ corresponds to $\log(x)+1$ binary write (e.g. to write $(1,0,0,0)$ corresponding to $8$).
In the best case (e.g. on $x=8$), the operator $x.inc()$ corresponds to exactly one binary write (e.g. to change the last bit of $(1,0,0,0)$ to $1$, giving $(1,0,0,1)$).

In a sequence of increments of the same integer object (e.g. enumerating all integers from $0$), the "best case" described above happens half of the time, and the worst case one every $n$ increment (i.e. after $1,2,4,8,16,...$ increments). A case requiring $i$ bits write happens $1/2^i$ of the time. Summing all those costs gives an amortized cost of $\sum_i i/2^i \in O(1)$. Hence the operator $inc()$ has a worst case complexity of $O(\lg n)$ but an amortized complexity of $O(1)$.

The notion of amortized analysis is well explained on wikipedia. You might want to see the page on the Potential method for more details.

Hope it helps!


In the most general sense, a key is a piece of information required to retrieve some data. However, this meaning plays out differently depending on exactly what situation you're dealing with.

In the contexts you mention, a key is a unique identifier for the complete data used to retrieve it from some location in the structure. Each key is associated with only one item, so it can be used to find a particular set of data. The data structure will usually be organized in such a way that finding the key is much more efficient than a linear search through all of the data. Sometimes the key is actually part of the data and stored along with it (like primary keys in the database); other times, it is segregated from the data itself (like in a hash map). The data structure will also often perform extra processing on the key (and only the key) to support its efficient searching algorithm (such as in a hash map, the key is converted into a hash code, or a database will index the primary keys using a B-tree).

In cryptography, a key is used in a sense more akin to physical keys used on locks. They're pieces of data required to obtain the original from the encrypted data (to "unlock" the data, so to speak).


Where to put the state in a two-stack push down automaton?

A configuration of a TM is usually defined as $uq\sigma v$, where $u\sigma v$ is the tape's content up to a cell from which there are only blanks, $q$ is the current state, and the head of the machine points at the letter $\sigma$. So the place of the state $q$ in the configuration $uq\sigma v$ is there simply to indicate at which letter the head points. Generally, a configuration holds a snapshot of the model during its run, including all information that is relevant to carry out the computation one step at a time.
Now consider a two-stack PDA $\mathcal{A}$, and think how to defined a configuration of it. Here, unlike TMs, we always point (in each stack) at the top of the stack, and therefore an indication to the stacks contents is sufficient - storing where the heads point does not add valuable information to help us compute the next configuration, given the current one. Specifically, the necessary information a configuration of $\mathcal{A}$ needs to hold are:
1- the content of the two stacks.
2- the current state.
3- the input left to be read.
So, we can define a configuration as a word of the form $ u q v \# w$, where $u$ is the content of the first stack, $v$ is the content of the second stack, $q$ is the current state, $w$ is the input left to be read, and $\#$ is a special charecter to indicate the end of $v$ and the beginning of $w$. Please note that the fact that $q$ is between $u$ and $v$ is not crucial. We could have defined a configuration of $\mathcal{A}$ as $qu\#v\#w$, and that makes no difference as long as we agree on which definition we stick. Anyway, I think the later definition is closer to being standard.


Yes, any PDA with $n>2$ stacks can be simulated by a pda with $2$ stacks. It is possible to show this without explicitly using Turing machines.

Assume that you have $n$ stacks, with contents $\alpha_1$ to $\alpha_n$. Store all these stacks on top of each other, with special separator symbols $\square_i$. So a single stack contains $\square_1\alpha_1 \dots \square_n\alpha_n$ (top left). Now assume that I want to perform an operation on stack $k$ (look at the top, check it is empty, push or pop symbols). In order to do this use the second stack. Move all stacks up to the $k$th to the second stack (popping from the one pushing to the other). The two stacks are now $\square_1\alpha_1 \dots \square_k\alpha_k$ and $\alpha^R_n\square_n\dots \alpha^R_{k+1}\square_{k+1}$. it is now easy to operate on stack $k$ (since it is on top of one of the stacks). and in general we continue moving the $n$ stacks around between the two stacks to  continue the simulation.


Algorithm to find the first person in front of $A$ that is shorter than $A$

There is an $O(n)$ solution for building such array using stack.

Starting with a brute force algorithm, you can traverse the array from right to left and for each element in the array, try all elements to the right of it until finding a smaller number. That would be $O(n^2)$.

To get an $O(n)$ solution, instead of each element having to look at all the elements to the right of it. We would just maintain a list of special elements by noticing that whenever a number at position $x$ sees a larger number to the right of it (at position $y$ where $y$ > $x$), the larger number is of no use anymore.

To prove that, we can assume for contradiction that element at position y was the $b_i$ of some future number. That means that $a_y < a_i$ but since $a_x < a_y < a_i$ and $x$ is between $i$ and $y$, then element $x$ would have been $b_i$ instead. Hence, a contradiction.

The algorithm to get $b_i$ would be to do the same as the brute force, but instead of just searching for a smaller element to the right, we will delete the larger elements that we meet on our way and break as soon as we find a smaller number. Simulating this efficiently can be done using a stack, where each $i$ keeps popping elements while the top of the stack is larger than $a_i$. The top of the stack after the pops will be $b_i$. $a_i$ is then pushed to the stack so that it will be seen by the next elements.

Complexity

The algorithm may still look as an $O(n^2)$ algorithm, but looking at the number of times that an array element is checked, we will find that each element is looked at for a constant number of times, since it is either pushed (once), popped (also once) or selected as $b_i$ (total of n for all a $b_i$). So the sum of operations is $O(n)$ for the algorithm.


What is the relation between NC and P/poly?

If you define NC as the class of problems computable using polynomial size, polylogarithmic depth circuits, then NC$\subseteq$P/poly, since P/poly is the class of problems computable using polynomial size circuits (without restrictions on the depth). Sometimes we also require the circuits to be uniform, and then we get the stronger conclusion uniform-NC$\subseteq$P. In both cases it is conjectured that the containments are strict.

In fact, since P-complete problems are complete with respect to very weak reductions, uniform-NC$\subsetneq$P if and only if a P-complete problem is not in NC. Wikipedia has a list of many P-complete problems.


TL;DR -- No, there is no better strategy than the simple strategy.  Here is the main idea of the proof. When there are not enough balls, there will be a "ball path" from a $k$-full bin to a bin with at most $k-2$ balls. The adversary can pass a ball from that full bin to that less full bin along that path, which can be done repeatedly until the number of $k$-full bins is reduced.

Reformulation in Graph theory

Suppose we are given a simple finite graph $G(V,E)$ with a function $w: E\to\Bbb Z_{\ge 0}$. We say there are $w(e)$ balls in edge $e$. Let $E_2$ be the (end-marked edge) set $\{(e,v)| e\in E, v\in e\}$. If $d:E_2\to\Bbb Z_{\ge 0}$ satisfies $w(e)=d(e,v_1) + d(e,v_2)$ for every edge $e=\{v_1,v_2\}$, we say that $d$ is $w$-distributing. Any $w$-distributing function $d$ induces a function, which we use the same symbol, $d:V\to\Bbb Z_{\ge 0}$, $d(v) =\sum_{v\in e}d(e,v)$. We say that $d(v)$ balls are in $v$. Given $k\in\Bbb Z_{\gt0}$, let $F_k(d)=\#\{v\in V|d(v)\ge k\}$, the number of $k$-full vertices by $d$.

(Erel-Apass Theorem) For any simple finite graph $G(V,E)$ and $w:E\to\Bbb Z_{\ge0}$, we have $\sum_{e\in E}w(e)\geq (2k-1) \min_{w\text{-distributing }d}F_k(d)$

Imagine each vertex is a bin. For each edge $e=\{v_1,v_2\}$, $w(e)$ ball-pairs are put into $v_1$ and $v_2$, each of which getting $w(e)$ balls. Among these $w(e)$ ball-pairs, the adversary may take away $d(e,v_2)$ balls from $v_1$ and $d(e,v_1)$ balls from $v_2$. The end result is the same as if, given all empty bins initially, for each edge $e=\{v_1, v_2\}$, $w(e)$ balls are put into it and, then, $d(e,v_1)$ and $d(e,v_2)$ balls are distributed to $v_1$ and $v_2$ respectively by the adversary.  Hence, Erel-Apass theorem says that in order to ensure $t$ k-full bins after a smart adversary's removal, at least $(2k-1)t$ pairs of balls are needed. In another word, an optimal strategy to have the maximum possible number of full bins left is indeed the "simple strategy", which repeatedly fills a different pair of bins with $2k-1$ ball-pairs until we do not have enough balls to repeat.

Proof of the theorem

For the sake of contradiction, let $G(V,E)$ and $w$ be a counterexample whose number of vertices is the smallest among all counterexamples. That is, there is $w$-distributing $m$ such that $F_k(m)$ is minimal among all $F_k(d)$ of $w$-distributing function $d$. Furthermore,
$$\sum_{e\in E}w(e)\lt (2k-1)F_k(m)$$

Let $V_s=\{v\in V | m(v)\le k-2\}$. Let $V_\ell=\{v\in V|m(v)\geq k\}$. So $F_k(m)=\#V_\ell$.

Claim one: $V_s\neq\emptyset$.
Proof of claim one. Suppose otherwise that $V_s$ is empty.
$$ \sum_{v\in V}m(v)= (k-1)\#V +\sum_{v\in V}(m(v)-(k-1))
                    \ge (k-1)\#V + \#V_\ell \gt (k-1)\#V$$
Let us also reuse $w$ as a function from $V$ to $\Bbb Z_{\ge 0}$ such that $w(v)=\sum_{v\in e}w(e)$ for any $v\in V$.
$$\begin{align}
\sum_{v\in V}w(v) &=\sum_{v\in V}\sum_{v\in e }w(e)
                  =\sum_{e\in E }\sum_{v\in e}w(e)
                  =\sum_{e\in E}2w(e)
                  =2\sum_{e\in E}w(e)\\
                  &=2\sum_{e\in E }\sum_{v\in e}m(e,v)
                  =2\sum_{v\in V}\sum_{v\in e }m(e,v)
                  =2\sum_{v\in V}m(v)\\
                  &\gt 2(k-1)\#V
\end{align}$$
So there must be a vertex $b$ such that $w(b)\ge 2k-1$.

Consider the induced setup $G'(V', E')$ and $w'$, where $V'=V\setminus\{b\}$, $G'(V', E')$ is the induced graph $G[V']$ and where $w'=w|_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d_{d'}$ where $d_{d'}$ is the same as $d'$ on $E'$ while $d_{d'}(e, b)=w(e)$ for every edge $e$ adjacent to $b$. Note that $F_k(d_{d'})= F_k(d') + 1$ since $d_{d'}(b)=\sum_{b\in e}d_{d'}(e,b) = \sum_{b\in e}w(e)=w(b)\ge 2k-1\ge k$. Then
$$\begin{align}\sum_{e\in E'}w'(e)&\le\sum_{e\in E}w(e) - w(b)\\
  &\lt (2k-1)F_k(m) -(2k-1)\\
  &=(2k-1) \left(\min_{w\text{-distributing }d}F_k(d) -1\right)\\
  &\le (2k-1) \left(\min_{w'\text{-distributing }d'}F_k(d_{d'})-1\right)\\
  &\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d')
\end{align}$$
So, $G'(V', E')$ and $w'$ is a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot true by our assumption about $G(V,E)$ and $w$. So claim one is proved.

For any vertex $v$, define $v$ $d$-reachable from vertex $u$ if there is a path $u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$, $m\ge0$ such that $d(\{u_i, u_{i+1}\}, u_i)>0$. Let $V_r=V_\ell\cup \{v\in V|\exists u\in V_\ell \text{ and } v\text{ is } m\text{-reachable from } u \}$.

Claim two: $V_r = V$
Proof of claim two: Suppose $V_r\neq V$. For any vertex $v\in V_r$ and $u\notin V_r$, since we cannot reach $u$ from $v$,  if $\{v, u\}$ is an edge, then $w(\{v, u\}, v) = 0.$ Consider the induced setup $G'(V', E')$ and $w'$, where $v'=V_r$, $G'(V', E')$ is the induced graph $G[V']$ and where $w'=w|_{E'}$. For any $w'$-distributing function $d'$, we can extend it to a $w$-distributing function $d_{d'}$ where $d_{d'}$ is the same as $d'$ on $E'$ and the same as $m$ on other edges. Note that $F_k(d_{d'})= F_k(d')$ since all vertices with no less than $k$ balls inside are in $V_\ell\subset V_r$. Then
$$\begin{align}\sum_{e\in E'}w'(e)&\le\sum_{e\in E}w(e)\\
  &\lt (2k-1)F_k(m)\\
  &=(2k-1) \min_{w\text{-distributing }d}F_k(d)\\
  &\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d_{d'})\\
  &\le (2k-1) \min_{w'\text{-distributing }d'}F_k(d')
\end{align}$$
So, $G'(V', E')$ and $w'$ would be a counterexample whose number of vertices is smaller than the number of vertices in $G$. That cannot be true by our assumption about $G(V,E)$ and $w$. So claim two is proved.

Now let us prove the theorem.

Since $V_r=V$ and $V_s\neq\emptyset$, there is a path $u_0= u, u_1, u_2, \cdots, u_m, u_{m+1}=v$, $m\ge0$ with $m(u)\gt k$, $m(v)\leq k-2$ and $d(\{u_i, u_{i+1}\}, u_i)>0$. Let us construct a new $w$-distributing function $r(m)$ from $m$ so that
$$r(m)(e, u)= \begin{cases}
    m(\{u_i, u_{i+1}\}, u_i) -1 & \text{ if } (e,u)=(\{u_i, u_{i+1}\},u_i)\text { for some } 0\le i\le m\\
    m(\{u_i, u_{i+1}\}, u_{i+1}) +1 & \text{ if } (e,u)=(\{u_i, u_{i+1}\},u_{i+1})\text { for some } 0\le i\le m\\
    m(e,u) &\text{ otherwise }
  \end{cases}$$

$m$ and $r(m)$ agrees on all vertices except $v$ and $u$, $m(v)\lt r(m)(v)\le k-1$ and $r(m)(u)\lt m(u)$. We can apply this procedure on $r(m)$ to get $r^2(m)$. Repeating this $i$ time for some large enough $i$, we will obtain a $w$-distributing function $r^i(m)$ with $F_k(r^i(m))=0$. However, we have assumed that $F_k(m)>0$ is the minimum among $F(d)$ of $w$-distributing function $d$. This contradiction shows that we have proved the Erel-Apass theorem.


Paging: Does the page table of a process also gets swapped out when the process gets swapped out from main memory?

The below article include the answer of your questions, apparently this is possible using multi level page table.

https://www.8bitavenue.com/page-table-vs-inverted-page-table/


Is necessarily the following language not decideable

Take some undecidable language $A$ and choose $B=A'\bigcup \{\epsilon\}$. $B$ is also undecidable, and the rest of the proof is just as what you have already done.


How to interpret this formal language definition?

This is pretty standard notation for

$\qquad \#_a(w) = |w|_a = $ number of occurrences of $a$ in $w$.

Building a PDA for this language is straight-forward. Find a hint below.

   Use the stack to count $\#_0 - \#_1$ in the processed prefix of the input. Figure out how to model negative numbers.


Finding a vertex coverage that is also an independent set

This problem is called the independent vertex cover problem and it is solvable in polynomial time. Note that the set $S$ must be a vertex cover means that each edge has an endpoint in the set. On the other side, being an independent set means that each edge has at most one endpoint in the set. Hence, each edge has exactly one endpoint in the set. That means we are looking for the smallest possible subset of vertices $S$ such that $(S, V\setminus S)$ is a bipartition of the graph. This can be done in linear time since each connected component has either non or exactly one bipartition.

Here is also another solution of the problem based on a reduction to the 2-sat problem (also using the fact that each edge has exactly one endpoint in the set).

https://cstheory.stackexchange.com/questions/36707/smallest-vertex-cover-which-is-also-an-independent-set


You can reduce MAX-2SAT to Satisfiability (using Cook-Levin), which can then be reduced to Vertex Cover (Folklore).


Which algorithms can not be parallelized?

This article gives a number of problems that are easy to solve sequentially but difficult to parallelise: http://en.wikipedia.org/wiki/P-complete

The circuit value problem ("given a Boolean circuit + its input, tell what it outputs") is a good starting point — easy to understand, easy to solve with sequential algorithms, and nobody knows if it can be parallelised efficiently.


How to show that hard-to-compute Boolean functions exist?

There are only so many circuits using at most $m$ gates, say $f(m)$. If all Boolean functions on $n$ inputs could be computed using at most $m$ gates, then $f(m) \geq 2^{2^n}$, since there are $2^{2^n}$ Boolean functions on $n$ inputs. Hence if $f(m) < 2^{2^n}$ then there must be a function on $n$ inputs which cannot be computed using at most $m$ gates.

A Boolean circuit with $m$ unbounded fan-in gates can be simulated using at most $m^2$ binary gates. We can describe each binary gate by satisfying its inputs and its type (AND, OR, NOT), for a total of $O(m^4)$ possibilities per gate. This leads to a rough bound $f(m) = O(m)^{4m}$. If $m = C 2^n/n$ then
$$
f(m) = \exp O(m\log m) = \exp O(C 2^n),
$$
and so for an appropriate choice of $C$, we would get $f(m) < 2^{2^n}$. This shows that there are some Boolean functions which require at least $C 2^n/n$ gates to compute. It turns out that (up to the choice of $C$) this bound is tight. (So what you wrote in your post is actually wrong.)


Clique in P when the input graph's connected components have at most $3\log|V|$ vertices?

Indeed, it is:

Consider the input $G,k$. First, it is easy to verify that the sizes of the connected components are as required.
Now, if $k>3\log |V|$, then clearly there is no clique of size at least $k$.

Otherwise, we can find the maximal clique in each component by considering all the subsets of the component.

For a component of size $3\log |V|$, there are $2^{3\log |V|}=|V|^3$ possible subsets of vertices. Once we identified the maximal clique in each component, we can compare this size to $k$, and return the answer.


Help me resolve my doubts about infinities, exemplified by an example of non DFA acceptable language

Look at your general procedure: given a language $L$ and integer $n$ build a DFA that properly recognizes any string $x \in L$ with $|x| \leq n$. Note that the language you selected is not special, any language can be represented by a sequences of DFAs with one for each $n$. To see this, just build a tree DFA with $|\Sigma|^{n + 1}$ states with a state for every possible string of length $\leq n$ marking the ones in $L$ as accept states and the ones not in $L$ as reject states and then minimizing. (If you want an even simpler example, then note than for any $L = \cup_{x \in L} \{x\}$ and every $\{x\}$ is recognized by a DFA with $|x| + 1$ states)

The whole point of DFAs is that it is a finite object that recognizes an infinite object. In fact, this is the whole point of computer science in general: Turing Machines are a different kind of finite object that recognizes (or encode) a different (larger) set of infinite objects. This means that for a language to be recognized, you need a single machine that works for all strings in that language.

What you have shown is that $L_n = L \cap \Sigma^{ \leq n}$ is recognized by a DFA, but these are just finite languages and every finite language is recognized by some DFA. However, regular languages are not closed under infinite union (in fact, very few things of interest to computer scientists are closed under arbitrary infinite unions), so the simple fact that $L = \cup_{n = 1}^{\infty} L_n$ does not imply anything about $L$.


Describe a Monte Carlo algorithm for the Triangle Packing problem

Although I agree with Yuval, I'll try to get you started on the connection to their longest path approach. The goal is, given a graph $G$, to define a polynomial $P_G$ which is nonzero iff $G$ has $k$ disjoint triangles. If you could evaluate $P_G$ on an arbitrary point in the underlying field $\mathbb{F}$ in time $2^{3k}n^{O(1)}$ then Schwartz-Zippel gives you the desired result (assuming that the degree of $P_G$ is low enough compared to $|\mathbb{F}|)$.
Denote by $T$ the set of all length $3k$ vertex sequences $(v_1,...,v_{3k})$ such that for all $i$ satisfying $i=1\pmod 3$,  the triplet $(v_i,v_{i+1},v_{i+2})$ is a triangle in $G$. Now, it is not hard to see that if $\mathbb{F}$ has characteristic 2 then the following polynomial (over $|E|+3k|V|$ variables) is nonzero (i.e. has a nonzero coefficient) iff $G$ contains $k$ disjoint triangles:
$P_G(\pmb{x_e},\pmb{y_{(v,j)}})=\sum\limits_{(v_1,...,v_{3k})\in T}\sum\limits_{l\in S_{[3k]}}\prod\limits_{i\in[3k]}x_{(v_i,v_{i+1})}\prod\limits_{i\in[3k]} y_{i,l(i)}$
Where $S_n$ is the symmetric group. The hard part is evaluating $P_G$ without going over all possible sequences in $T$. The fact that we don't care about repetitions in sequences in $T$ will allow (after some considerable work in rewriting $P_G$) efficient dynamic programming to come into play. The rest pretty much follows the proof for the longest path case (after extending the sum to functions whose range is a subset of $[3k]$, the dynamic programming part would look a bit different, e.g. you would probably want to shorten the sequence by three elements at a time).


You got it right, I think.

$1 : N$ means: Any $A$ may be connected with any number of $B$, but every $B$ is connected to (exactly) one $A$.

Example: (Biological) Mothers and children.
$M : 1$ means the same, just reversed.
$M : N$ means that any $A$ may be connected with any number of $B$ and vice versa.

Example: Teachers and students.


Factoring algorithms after number field sieves

From the first line of Wikipedia's GNFS page:

"the general number field sieve (GNFS) is the most efficient classical
algorithm known for factoring integers larger than"

The following factorizations of RSA numbers used none other than the GNFS algorithm:

February 2020: RSA-250
December 2019: RSA-240
February 2020: RSA-232
August 2018: RSA-230
May 2016: RSA-220

Conclusion: The top researchers in the field are breaking factorization records using none other than GNFS (usually the CADO-NFS implementation). If there was a faster factorization algorithm for arbitrary semi-primes, surely the groups of Zimmerman and Lenstra would be using it, or at least mentioning it somewhere in their papers. GNFS is still the fastest for arbitrary semi-primes. For specific semi-primes like $p^2$ where $p$ is prime, there's faster algorithms such as doing the square root.
A more interesting question might be: What are some recent developments in the field of factoring numbers on classical computers? I might also be interested if there's anything promising out there that's been developed recently and might have a chance at beating GNFS one day. Also if you look at the above references, the authors will tell you of great achievements in improving implementations of the GNFS algorithm (for example the matrix step used to be harder than the sieving itself, but that was sorted out at around the time of factoring RSA-220).


Packing objects into bins to minimize the number of bins

This is the clique cover problem in disguise, and finding an optimal solution  NP-hard.


Extracting a spanning tree from a directed acyclic graph with minimum total distance between terminal nodes

Your problem is similar to the directed Steiner tree problem. In this problem we are given a directed graph, a set of terminal vertices and a specified root. The goal is to find a minimum cost tree that connects all terminal vertices to the root.

This is not exactly what you are asking for, but perhaps a solution to such a problem (or a suitable variant) is good enough.


What is the single type in a dynamic typing language?

The "single type" for Python is called "object" and described in https://docs.python.org/3/reference/datamodel.html:

Objects are Python’s abstraction for data. All data in a Python program is represented by objects or by relations between objects. (In a sense, and in conformance to Von Neumann’s model of a “stored program computer”, code is also represented by objects.)
Every object has an identity, a type and a value. An object’s identity never changes once it has been created; you may think of it as the object’s address in memory... An object’s type determines the operations that the object supports (e.g., “does it have a length?”) and also defines the possible values for objects of that type... The value of some objects can change. Objects whose value can change are said to be mutable; objects whose value is unchangeable once they are created are called immutable.

Of course, note that "type" and "value" are not used here in the same way as in Harper's book: Python's "type" is what Harper calls "class".


In these cases it's always a good idea to look at the statement of the master theorem. The statement on Wikipedia states regarding case 3 that if
$T(n) = aT(n/b) + f(n)$ where

$f(n) = \Omega(n^c)$ for some $c > \log_b a$ (i.e. $b^c > a$), and
$af(n/b) \leq (1-\epsilon) f(n)$ for some $\epsilon > 0$ and large enough $n$,

then $T(n) = \Theta(f(n))$.

Let's see whether the theorem applies in your two cases. In your first case $a = 3$, $b = 4$, and $f(n) = n\log n$. We have $f(n) = \Omega(n^1)$ and $1 > \log_4 3$, and furthermore $$3f(n/4) = 3(n/4)\log(n/4) \leq (3/4)n\log n = (3/4)f(n).$$
Both conditions are satisfied, and so we can conclude that $T(n) = \Theta(n\log n)$.

In your second case $a = b = 2$ and $f(n) = n\log n$ is the same. In this case $f(n) = \Omega(n^c)$ only for $c \leq 1$, whereas we need $c > \log_2 2 = 1$, so we cannot apply case 3. The second condition also doesn't hold, since $2f(n/2) = 2(n/2)\log(n/2) = n\log n - \Theta(n)$, and so it is not true that $2f(n/2) \leq (1-\epsilon) f(n)$ for any $\epsilon > 0$.

However, in this example case 2 of the master theorem applies, showing that $T(n) = \Theta(n\log^2 n)$.


Is it possible to do face recognition with just the eyes?

Recognising the right face is not the problem. Reliably rejecting the wrong face is.


Whats the best way to sort a dataset into groups by using a facial recognition algorithm that compares only 2 images at a time?

So it appears you actually have vectors over $\mathbb{R}^n$, one vector per face, and you want to group the vectors, using $L_2$ distance (Euclidean distance) to measure similarity.

There are a number of techniques for this.  See data structures for nearest neighbor search (https://en.wikipedia.org/wiki/Nearest_neighbor_search).  I would suggest that locality sensitive hashing might be a promising choice for your situation.  You could also look into clustering algorithms (though they will probably still require nearest neighbor search as one step of their working).


Lower upper bound on # variables in k-SAT with m clauses

If you want to prove the worst-case running time of your algorithm, you probably don't need to prove that.  It's probably enough that there exists instances of SAT with (say) $\frac12 mk$ variables that are NP-hard; and that can be proven.

When each variable occurs only twice in the formula, SAT can be solved in polynomial time (via resolution).

With the restriction that each variable can occur up to three times in the formula, SAT remains NP-hard.  (Proof: start with an ordinary CNF formula $\varphi$.  If $x_i$ appears $k$ times, introduce variables $x_{i,1},\dots,x_{i,k}$, replace the $j$th occurrence of $x_i$ with $x_{i,j}$, and add clauses for $\neg x_{i,1} \lor x_{i,2},\neg x_{i,2} \lor x_{i,3},\dots,\neg x_{i,k-1} \lor x_{i,k}, \neg x_{i,k} \lor x_{i,1}$.)

Therefore, there exists a class of instances of $k$-SAT with $m$ clauses and $\frac{1}{3} mk$ variables, such that solving those instances is NP-hard.

To answer your original question, there is no useful answer to your original question.  For all $\varepsilon>0$, there exists a class of instances of $k$-SAT with $m$ clauses and $(1-\varepsilon)mk$ variables that is NP-hard.   In particular, take an ordinary CNF formula $\varphi$ with $n$ variables and then just append useless clauses of the form $x_{t} \lor x_{t+1} \lor \cdots \lor x_{t+k}$; each useless clause mentions $k$ new variables that appear only in that one clause and nowhere else.  The resulting formula is exactly as hard as $\varphi$, but now has a number of variables that is an arbitrarily large fraction of $mk$.


Algorithm to find most nodes in distinct cycles

Your problem is NP-complete (formulated as a decision problem), by reduction from SAT. For simplicity, I describe a reduction that uses self-loops, but they can easily be avoided.

Given an instance of SAT, create nodes for each variables and each clause. For each assignment of each variables, add directed cycles connecting the variable node with clause nodes satisfied by this assignment, for all possible such subsets (the empty subset corresponds to a self-loop). Since there are no parallel edges, we can also think of these cycles as resulting from a single cycle going through all satisfied clauses by taking all possible shortcuts not avoiding the variable node.

In the resulting graph, it is possible to cover all nodes of and only if the formula is satisfiable, completing the proof.

In practice, it might be possible to find good solutions heuristically, but that could depend on the nature of your instances.


If P is a property of turing machines, does P $\leq_T$ COUNT_P imply that P $\in$ RE $\cup$ coRE?

Let $L \subseteq \mathbb{N}$ be a set of your choice, let $N(M)$ be the number of states in a Turing machine $M$, and let $P = \{ \langle M \rangle : N(M) \in L \}$. Then $P$ reduces to $\mathsf{COUNT}_P$, but $P$ can be arbitrarily hard.


How do we show $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x . x)$ in lambda calculus?

The two terms are in the same $\alpha$-equivalence class.
In lamba calculus, we can rename bound symbols without changing the meaning of the term.
$\lambda x.x$ and $\lambda y.y$ both mean "a function that takes one input and returns it". A variable is bound by the first matching lambda above it in the term-tree.
We often $\alpha$-rename bound variables before $\beta$-reduction to make sure unbound variables do not get caputured after the reduction step.

To answer your question:

$$\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda x.x (\lambda x'.x')$$ (rename bound $y$)
$$\equiv_{\alpha} \lambda y.y (\lambda x'.x')$$ (rename bound $x$)
$$\equiv_{\alpha} \lambda y.y (\lambda x.x)$$ (rename bound $x'$)
This gives us $\lambda x . x (\lambda y .y) \equiv_{\alpha} \lambda y.y (\lambda x.x)$


Does a distance matrix have to be Euclidean in order to be clustered by an average-linking algorithm (UPGMA)?

While you can modify any algorithm as you see fit, in its pure form UPGMA has the following underlying assumptions at work:

UPGMA (Unweighted Pair-Group Method with Averages), arithmetic average - the average distance between elements of each cluster (weighted by the number of elements).

For example, (AB) and C+(DE) = (55+3x45)/3 = 63.33

Additional Comparative Algorithmic Context

Below is a list of algorithms and their general framework as it relates to each algorithm:

SINGLE (Single-link method) – brings together the closest elements.
WPGMA (Weighted Pair-Group Method with Averages), arithmetic average (not weighted by the number of elements).
WPGMC (Weighted Pair-Group Method with Centroid Average), centroid average (assumes dissimilarity).
WPGMS (Weighted Pair-Group Method with Spearman Average), Spearman's average (assumes correlation).

Reference for Modifying UPGMA

The paper below is a wonderful resource for "what-if" scenarios as it relates to UPGMA:

Vavrek, M. J. (2016). A comparison of clustering methods for biogeography with fossil datasets. PeerJ, 4, e1720. http://doi.org/10.7717/peerj.1720


The difference appears to be that "process" is a well-defined term with a specific meaning that is universally understood, whereas "task" is ambiguous and means different things to different people.

The following Stack Overflow questions on the same topic support this:

https://stackoverflow.com/questions/3042717/what-is-the-difference-between-a-thread-process-task
https://stackoverflow.com/questions/2560939/task-vs-process-is-there-really-any-difference

Microsoft Windows certainly conflates the two terms—the Task Manager is used to administer processes.


Map
applies a unary function to each element in the sequence and returns a new sequence containing the results, in the same order

$$\mathrm{map}\colon (E\to F) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle F\rangle\,.$$

Filter tests each element with a unary predicate. Elements that satisfy the predicate are kept; those that don’t are removed.

$$\mathrm{filter}\colon (E \rightarrow \mathrm{boolean}) \times \mathrm{Seq}\langle E\rangle \rightarrow \mathrm{Seq}\langle E\rangle\,.$$

Reduce combines the elements of the sequence together, using a binary function. In addition to the function and the list, it also takes an initial value that initializes the reduction, and that ends up being the return value if the list is empty.

$$\mathrm{reduce}\colon (F \times E \rightarrow F) \times \mathrm{Seq}\langle E\rangle \times F \rightarrow F\,.$$

Example:

\begin{align*}
\mathrm{result}_0 &= \mathrm{init} \\
\mathrm{result}_1 &= f(\mathrm{result}_0, \mathrm{list}[0]) \\
\mathrm{result}_2 &= f(\mathrm{result}_1, \mathrm{list}[1]) \\
&\ \ \vdots\\
\mathrm{result}_n &= f(\mathrm{result}_{n-1}, \mathrm{list}[n-1])
\end{align*}

Hence you can see it as a function $\mathbb{R}^n \rightarrow \mathbb{R}$

Source: http://web.mit.edu/6.005/www/fa15/classes/25-map-filter-reduce/


Context-sensitive grammars without permutation rules

You have the Koruda normal form in mind. It is indeed often useful, in particular in simulation LBAs.

However, many definitions of CSGs (including Chomsky's) are different; they require rules to have the form

$\qquad \alpha A \beta \to \alpha \gamma \beta$.

You can see how this precludes "permutation rules".

Obtain a concrete grammar by applying the simulation you find in a proof that KNF is equivalent to the classical definition.


What is the difference between a page and thread?

You're looking at very vague descriptions and asking "What's the difference between these things that haven't been described properly?" For a more detailed understanding, you should, well, look for more detail, which is widely available.

A page is a block of memory; a thread is a sequence of instructions to be executed.


Are there any established methods for generating random graphs/networks that are both planar and meshlike?

You could take the Delaunay triangulation of a random set of points (or, if you want almost lattices, a perturbation of something regularly defined) and remove some edges if you want.
This won't give you a small-world graph, but no lattice-like thing would. If you want something like this, you'll have to have some fractal properties anyway (if the connections are "nearby", then you'll need a lot of connections to go far).
If you want something scale-free, you can generate a Delaunay triangulation hierarchy instead -- which is a beautiful and useful tool of computationnal geometry so you'll find lots of references. The idea is to have a Delaunay triangulation on a small number of point, and then a Delaunay triangulation inside each triangle, and again, etc.


What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?

I think there's a slight misunderstanding in the question. The phrase is "optimal substructure", not "optimal substructures". It's not a matter of looking at the individual substructures (e.g., regions of the grid you're trying to tile) and saying, "This one's optimal", "This one's optimal", "This one isn't". Rather, it's a matter of looking at the structure and interactions of the subproblems and saying, "The substructures of this problem (i.e., the subproblems) interact in a way that lets me find an optimal solution easily."

I also don't think this is a great example for greedy algorithms, since greedy algorithms are naturally somewhat recursive and it's so easy to domino-tile a grid iteratively that it feels artificial to force it into a recursive solution. But here goes...

One example of optimal substructure is that, if you can divide your grid into rectangles $A$ and $B$ and you can perfectly tile $A$, then an optimal tiling of the whole grid can be made from the perfect tiling of $A$ along with an optimal tiling of $B$.  This gives the following greedy algorithm.

function tile (int width, int height, int startrow)
if (startrow <= height-1)
    perfectly tile rows startrow and startrow+1 like this | | ... |
    tile (width, height, startrow+2)
else if (startrow == height) then
    tile the last row like this -- -- ... -- , with one empty square
    at the end if width is odd
/* else startrow > height and there's nothing to do */

Note that this just produces tilings like this one for a $7\times3$ grid,

| | | | | | |
| | | | | | |
--- --- ---

which is exactly what you'd do iteratively.


How does one make an unambiguous context-free grammar for arithmetic expressions?

Indeed you made a step to resolve ambiguity, but your solution does not give a fully unmabiguous grammar yet. The string $x+x+x$ can be parsed in two different ways, like $x + [x+x]$ or like $[x+x]+x$, where the brackets indicate parses. As far as I see your solution resolves semantical ambiguities (it fixes the relative order of + and x) but not the syntactical ambiguity. So obtaining an umambiguous grammar is not the only goal for an example like this: we want to respect meaning (here operator precedence). (Perhaps there is more official terminology for that)

Your example is a familiar one, and is used in wikipedia/Syntax diagram:

<expression> ::= <term> | <expression> "+" <term>
<term>       ::= <factor> | <term> "*" <factor>
<factor>     ::= <constant> | <variable> | "(" <expression> ")"

Probably you will know that not every grammar has an unambiguous equivalent, so no general approach is possible.


If by pieces one means possible stages that the instruction can be split into. For example, like this "short" Classic RISC pipeline with five stages:

Fetch Instruction Stage: Fetch the instruction.
Decode Instruction Stage: Decode the instruction.
Execute Stage: Execute the instruction.
Memory Access Stage: Access (read/write from/to) the memory.
Writeback Stage: Write results to the CPU registers.

Then a short pipeline means that the instruction is split into a low amount of these stages (pieces), but the amount of hardware and time spent in each stage will actually increase (length of the pieces) compared to if there were more stages.


Asymptotic expected runtime of Randomized Algorithm

As you mention, it is easy to prove by induction that the overall runtime is $O(n^2)$. If we don't have any more information, that's (almost) all we can deduce. For example, suppose that at each instance we pay a cost of $O(1)$. The running time will then be $O(n)$. In order to make progress, we have to assume that at each instance we pay a cost of $\Theta(n)$. In that case, we can argue as follows:

Since each "jump" is $O(1)$, it takes $\Omega(n)$ steps (on average) to reach $n/2$.
At each of these $\Omega(n)$ steps, we pay a cost of $\Omega(n)$.
Hence the total expected cost is $\Omega(n^2)$.

This is not a rigorous argument, but it can be turned into one if you're careful enough.


It is a variant of bubble sort, however the endpoints of the array shift throughout the progress of the algorithm.

In particular it maintains the following invariant:

  at the end of the $i$-th iteration, the elements in indices $1..i$ are sorted.

At the first step it finds the maximal element and puts it in index 1.
(prefix length =1). Then, at every iteration $i$ it adds the element in position $i$ to the prefix, and performs a (degenerate) bubble sort on the first $i$ indices. This bubble sort takes only one step since except for the one new element, the other $i-1$ elements are already sorted. The maximal element will now be at position $i$. The length of the sorted prefix keeps increasing at every iteration until the entire array is sorted.

I don't know if this sorting approach has a name. It looks like a type of insertion sort.


How to compare an element with other elements within an array efficiently for a condition

In the general form you present, you have $\Theta(n^2)$ things to compare so you need $\Omega(n^2)$ time. If you know more about the arrays or the comparison operator (e.g., the arrays are sorted and the comparison is $<$ or $>$) then you can probably do something better but, without more restrictions, there's no hope.


Does basic 2 PL always ensure conflict serializability?

No,

If you use 2PL protocol you are guaranteed to have a conflict-serializable schedule but there are conflict serializable schedules which may not honour 2 PL protocol i.e. locking data items in the growing phase and releasing them in the shrinking phase.


Algorithm Analysis: Expected Running Time of Recursive Function Based on a RNG

How does the recursive formula for $E[T(n)]$ compare between this algorithm and randomized quicksort? They are very similar, which might lead one to believe that the running time of your algorithm is $\Theta(n \log n)$. In fact, the recursive formula for the run-time is so similar to the one for quicksort, that you could use that fact in itself as a proof. There are more elegant ways to prove it, but you can also prove it by induction.

$$ T(n) \leq bn + \frac{1}{n}\sum_{k = 1}^n T(k) + T(n-k)
$$

$$ = bn + \frac{2}{n}\sum_{k = 1}^{n-1} T(k).
$$

Suppose (induction hypothesis) that $T(i) \leq ci \ln i$ for $i \le n - 1$.

Then use the standard trick of bounding a sum by an integral:
$\sum_{i=1}^{n-1}f(i) \leq \int_1^n f(x) dx$.

The rest of the proof works like a standard proof by induction with just a little algebra.

Here's a nice source for this and other proofs of the running time of quicksort, and the techniques apply to this problem as well.

Notes on randomized quicksort analysis


In principle it could be that $2n^2 = 8n\log n$ could have several solutions. However, this doesn't matter much: the derivative of $n/\log n$ is
$$
\frac{\log n - 1}{\log^2 n},
$$
and so if $2N^2 \geq 8N\log N$ for some $N \geq e$, it follows that $2n^2 \geq 8n\log n$ for all $n \geq N$.
Plugging in small values of $N$, we see that $2N^2 > 8N\log N$ for $N = 9$.

Here is an alternative proof. We first prove that if $n = e^k$ and $k \geq 4$ is an integer, then $2n^2 \geq 8en(\log n + 1)$. You can calculate that it holds for the base case $k = 4$. Assuming that it holds for some $k \geq 4$, we prove it for $k + 1$. The induction hypothesis implies that
$$
2e^{2(k+1)} = e^2 \cdot 2e^{2k} \geq e^2 \cdot 8ee^k (k+1) = 8ee^{k+1} (k+2) \cdot e \cdot \frac{k+1}{k+2}.
$$
To complete the proof, it suffices to check that $e (k+1)/(k+2) \geq 1$, or equivalently, that $e \geq (k+2)/(k+1) = 1 + 1/(k+1)$, which trivially holds since $k \geq 4$.
Now let $n \geq e^4$ be arbitrary, and let $k = \lfloor \log n \rfloor$. Then
$$
2n^2 \geq 2(e^k)^2 \geq 2ee^k(k+1) > 2n\log n.
$$


How many combinations will be generated if below conditions are put?

$2^{n-1}-1$

Hint: 1) if you are summing with $k$ numbers $x_1,x_2,.., x_k$ note that once you choose upto $k-1$, last selection is forced on you as the next ascending number to $x_{k-1}$.
2) You are allowed to choose first $k-1$ numbers from n-1 numbers


KD-Tree implementation with lat/lon coordinates

Short answer: No, you will not get the same results.

It does not matter what coordinate system or what geographic standard you are using, it is not possible to make projection from sphere into rectangle and save all data (angles and distances) at the same time.
Haversine formula is prepared to operate on circles, 3D distance on sphere, while Euclidean distance will treat them as 2D points, so the result must differ.

Haversine is one of methods to get actual distance on sphere, to use it on Earth, it is only approximation so in such case I would suggest Vincenty formula.

The errors depend on coordinates given and the distance between points.

Take reference point $A =\{40^{\circ}N, 40^{\circ}E\} = \{40, 40\}$, $B =\{42^{\circ}N, 40^{\circ}E\} = \{42, 40\}$, $C =\{40^{\circ}N, 42^{\circ}E\} = \{40, 42\}$, treating them as $X, Y$ tells that they are equidistant - this is how Euclidean distance would see raw coordinates.

According to Haversine formula distance from $A$ to $B$ is ~$222.4 km$ (~$222,108 km$ Vincenty), distance from $A$ to $C$ is ~$170.4 km$ (~$170,784 km$ Vincenty), so it kinda fails.

The idea with ruler on the map, this gets heavy, it will fail as the above, but it depends on map projection (errors change, some projections save angles, some tries to save distances).


connected components - determining "groups" in Go

To count connected groups

Form an undirected graph, with one vertex per location on the board, and an edge between each two locations are are adjacent (horizontally or vertically).  Then, use any standard algorithm for connected components.  See https://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29 or your favorite CS algorithms textbookk.

You'll probably want to run the algorithm twice: once for x's (build a graph where you retain just the vertices with x's on them, and find all connected components), and once for o's (build a graph where you retain just the vertices with o's on them, and find all connected components).

To count liberties

If I understand the definition, this looks like a simple matter of programming.  Find a connected component of x's, look at each cell which is adjacent to it, and count how many are empty.  That's straightforward programming -- no fancy algorithms needed.  Programming questions are better on StackOverflow, but make sure you show your effort.


Why are regular expression quantifiers greedy by default?

A regular expression, as the term is used here, is a mathematical construct; it is the formalism used to define regular languages. In that context, the Kleene star operator is neither greedy nor abstemious. Rather, it is non-deterministic: it will match as many times as necessary.

It's worth pointing out here that regular expressions define a "language", not a substring. In that sense, the regular expression matches (or recognises) the entirety of a sentence.

Using regexes to find substrings was a (very useful) adaptation of a theoretical concept to practical programming problems. But it introduces an ambiguity which was not present in the original: if the regex can match more than one different substring, which one should it choose?

The original regex libraries all chose the first matching substring (in a left-to-right scan), and of those matches which all start at the same position, they chose the longest one. These are the Posix semantics for regular expressions, which also define how subpatterns ("captures" between parentheses) correspond to substrings of the matched string. ("Captures" form no useful part of the theoretical model of regular expressions.)

The regular expression formalism has the enormous advantage that it can be compiled into a Deterministic Finite Automaton (DFA) which can then be used to perform a match -- or even a substring search -- in linear time. In effect, the DFA recognizes all possible matches in parallel; it is easy to make it recognize the longest match, by simply continuing until no further advance is possible. It would also be easy possible to recognize the shortest match, although that is not as common as you might think. (Consider, for example, recognizing numeric or identifier-like tokens: you really want to match the longest possible string.)

However, implementing abstemious repetition is not the same as implementing shortest match. Rather, it requires ordering possible matches by examining a subcomponent of the match. Since regular expressions do not need to be deterministic in submatches (and usually are not), ordering by subcomponent is non-trivial; it requires significant extra memory and time because many alternative partial matches may need to be remembered during the scan.

Once you have substring matches, possibly with captured submatches, you need to start worrying about resolving these ambiguities. And the Posix semantics are not always what are desired. Sometimes -- often, even -- one would want to find the shortest matching substring. (As in the BEGIN.*?END example you mention.)

Consequently, many regex libraries do not use this algorithm, preferring a backtracking recursive solution. One of the advantages of the backtracking algorithm is that it can cope with a number of extended regex operators which cannot be implemented with a DFA, including back-references which are not even context-free (in general). On the flipside, these operators can introduce pathological slow-down, and it is relatively easy to craft regexes which take exponential time to do a search. If you allow user-supplied ("tainted") regexes, this is a vector for DoS attacks. Even if you don't allow tainted regexes, you sometimes have to think carefully about how to write a given regex in order to produce as efficient a search as possible.

Over the years, regexes have drifted further and further away from their theoretical regular language roots. However, there are still contexts in which the original formulation and its guaranteed linear time complexity are useful:

Lexical scanners, in which the regular expressions are not dynamic and therefore are usually compiled into the scanner. Since simple regular expressions are perfectly adequate for tokenising most programming languages, the efficient linear-time algorithm is preferred.
As mentioned, tainted regular expressions, such as on-line search engines. See, for example, Russ Cox's re2 library, based on a (re-)discovery of the linear-time algorithm, which he wrote in order to protect the Google Code search engine from potential denial of service attacks.


Why splitted text files is bigger than a large one with the same content?

Filesystem overhead.

Every time you create a file, the filesystem reserves space on disk to store the file name, and other metadata like its permissions, creation date, etc. It also has to maintain a sort of index of all the (possibly sparse) blocks occupied by each file. The index might be a simple list or a tree, depending on the filesystem.

Finally, note that most filesystems can not allocate only a portion of a block for a file, so the allocated space needs to be rounded up to the block size. This rounding affects both the file blocks, and the index blocks.


Lambda Calculus as a branch of set theory

It's false. The $\lambda$-calculus arose through efforts to understand foundations of mathematics. Nowadays some people mistakenly equate foundations with set theory. The Stanford Encyclopaedia of Philosophy has a very good writeup on the $\lambda$-calculus, as well as its history, I recommend it.


Algorithm for packing various shapes inside of a rectangle

As pointed out by the other answer, this is an example of bin packing, a type of problem that is NP-complete.

Skiena Section 17.9 reports:

  Fortunately, relatively simple heuristics tend to work well on most
  bin-packing problems.

The same source provides the following heuristic recommendation:

  Analytical and empirical results suggest that first-fit decreasing is
  the best heuristic. Sort the objects in decreasing order of size, so
  that the biggest object is first and the smallest last. Insert each
  object one by one into the first bin that has room for it. If no bin
  has room, we must start another bin. In the case of one-dimensional
  bin packing, this can never require more than $22\%$ more bins than
  necessary and usually does much better. First-fit decreasing has an
  intuitive appeal to it, for we pack the bulky objects first and hope
  that little objects can fill up the cracks.

  First-fit decreasing is easily implemented in $O(n \ \text{lg} n + bn)$
  time, where $b \leq min(n,m)$ is the number of bins actually used.
  Simply do a linear sweep through the bins on each insertion. A faster
  $O(n \ \text{lg} n)$ implementation is possible by using a binary tree
  to keep track of the space remaining in each bin. We can fiddle with
  the insertion order in such a scheme to deal with problem-specific
  constraints.

I recommend reading the original material in its entirety.


Show that a language is decidable iff some enumerator enumerates the language in lexicographic order

It's easier to think of $A$ as a list of natural numbers. If $A$ is decidable, then we can list all numbers in $A$ in increasing order by just testing all of them in order – Is $0 \in A$? Is $1 \in A$? And so on.

Now let us show that if $A$ can be enumerated in increasing order, then we can decide $A$. Let us try to use the following algorithm:

  On input $n$, enumerate all integers in $A$ in increasing order until a number $m \geq n$ appears. If $n$ has appeared, then clearly $n \in A$. If $n$ has not appeared, then $n \notin A$.

To see why the last point holds, suppose that $n=5$, and the enumeration starts $2,3,6$. At the point when we see 6, we know that 5 is never going to appear.

There is one problem with this algorithm – if $A$ is a finite language, then a number $m \geq n$ might never appear. Indeed, suppose for example that $A = \{2,3,5\}$ and that $n=6$. We see $2,3,5$, and then wait forever for a larger number to appear. We fix this problem in the following way:

If $A$ is finite, it is clearly decidable.
If $A$ is infinite, then the algorithm described above always terminates (why?).

Unfortunately, given just an enumerator for $A$, we (provably) cannot know whether $A$ is infinite or not, and so we don't know which of the two cases to use. Fortunately, this does not matter for the proof. All we need to do is show that if $A$ has an enumerator, then it has a decider. There is no requirement to turn an enumerator for $A$ into a decider for $A$ in a uniform fashion.


Suppose that the queue consists of elements $Q[a],\ldots,Q[b]$, where $Q = Q[1],\ldots,Q[n]$ is an array of length $n$. If $a \leq b$ then the queue contains $b-a+1$ elements, and if $a > b$ then the queue contains $b-a+1+n$ elements.


Karp hardness of a clique with given number of outer-incident edges

Our problem is $NP$-complete by a reduction from Exact Cover by $3$-sets ($\mathrm{X3C}$).

Given an $X3C$ instance with the universe set $U=\{e_1,e_2,\cdots,e_n\}$ and collection of $3$-sets $\mathcal{C}=\{s_1,s_2,\cdots,s_m\}$, we create an undirected graph $G$ as follows.

For each element $e_i$, create a vertex (which will be referred to by the same name).

For each $3$-set $s_j$, create a vertex (which will also be referred to by the same name).

Connect $e_i$ and $s_j$ whenever $e_i\in s_j$.

Connect $s_{j_1}$ and $s_{j_2}$ whenever they are disjoint.

Pick some large enough $M$, connect each set-vertex to dummy vertices to make sure that every set-vertex is of degree $M$.

Call the obtained graph $G$. Now, set $k=n+(M-3-\frac{n}3+1)*\frac{n}3$. The reduction then outputs an instance, namely $(G,k)$.

Suppose there exists an exact cover for the $X3C$ instance, we can easily form a solution to our problem by taking all the set-vertices of the exact cover. Clearly, this is a clique since every pair of $3$-sets in an exact cover needs to be disjoint. It has exactly $k$ outer-incident edges.

Conversely, if there exists a clique with $k$ outer-incident edges then every vertex of this clique needs to be set-vertex. Indeed, if there is any element-vertex in the clique, then the size of the clique is equal to the number of $3$-sets that includes that element plus one (the element-vertex itself). But then the size of this clique is only $4$, since $X3C$ is still $NP$-complete when each element is included in at most three $3$-sets. So, this is a clique of set-vertices. Thus, they are pairwise-disjoint. With $k$ outer-incident edges, the size of this clique must be exactly $\frac{n}3$. This is due to the fact that $M$ can be large enough (still polynomially) so that the binomial defining $k$ (in variable $x$, the size of the clique) is monotone in $[1,\cdots,m]$.


Searching and inserting in $O(n)$ when $n$ is the size of the key

I suppose someone, somewhere, did somehow the same thing but better (however, I did not find it).

What you describe is called a trie. For practical implementation you might take more than one bit at each level (e.g. take two bits and give each node four children).

  1: I suppose I still can use red-black trees, but comparison between two sequences of bits of length $n$ would be $O(n)$, and then INSERT and SEARCH would become $O(n^2)$, which is not nice.

There is potentially room for some subtlety here. If you record for each child node the bit index at which its key differs from the parent's, can you get it down to $O(n)$? I haven't thought through the answer myself, but it seems plausible that you'd essentially get a self-balancing trie-like structure, and might be an interesting exercise to attempt.

Finally, if you expect your map to be sparsely populated (i.e. to have much fewer than $2^n$ elements) it might be worth thinking about hashing.


You need to solve simple formula

$\sum_{i=1}^N\sum_{j=1}^i\sum_{k=i}^j1$

this will give you overall result of

$\frac{1}{6}N(N+1)(N+2)$

Math is easy to do here but I used Wolfram Alpha


Since $2^{n-1} = \Theta(2^n)$, in (CS-style) asymptotic analysis the two functions are equivalent. They have the same "order of growth" from the point of view of asymptotic analysis.

When giving big O upper bounds, we often want to suppress lower-order information. Therefore we sometimes write $\tilde{O}(n)$ instead of $O(n\log n)$ or of $O(n\log^2 n)$, and $\tilde{O}(2^n)$ instead of $O(n2^n)$. Generally speaking, $\tilde{O}$ hides (poly)logarithmic factors, that is, $\tilde{O}(f(n))$ is the same as $O(f(n) \log^{O(1)} f(n))$.

A bound of the form $\tilde{O}(2^n)$ is an exponential bound, since $\tilde{O}(2^n) = O(3^n)$ (indeed, $O((2+\epsilon)^n)$ for any $\epsilon > 0$). In fact, sometimes when saying exponential we also allow functions of the form $2^{n^2}$ in which there is a polynomial in the exponent; and sometimes we mean it in the strict sense of $O(c^n)$ for some constant $c>1$.

Finally, let me mention that complexity classes are about the complexity of problems, not the order of growth of functions. For example, the complexity class $\mathsf{P}$ consists of decision problems solvable in polynomial time. It is not the same as the class of all polynomials.


What is the advantage of seperate chaining over open addressing?

Suppose that you have a very large number of sufficiently uniform elements, $n$, that you want to hash. We want to minimize lookup time, obviously.

If we use separate chaining with $m$ linked lists, our lookup time will be, on average, $O(n/m)$ since we have $n$ elements and $m$ buckets. The actual lookup time depends on whether our input set is sufficiently uniform or not, but for the sake of simplicity we can assume that it is. What are the downsides of this? Linked lists and most other data structures that we would use to do this make heavy use of pointers. A single query takes $O(n)$ pointer dereferences.

Now consider two typical methods of open addressing: linear probing and quadratic probing. Linear probing traverses the space allot for open addressing and places the element that it is hashing at the first available memory location (at the $i^\text{th}$ step, we look at index $i$ to see if it is free). Quadratic probing traverses by incrementing the index by $i^2$ on each step. This can lead to immense speed-up due to its cache-friendliness (as mentioned in the first comment, this is called spatial locality -- I'd suggest reading this if you're unfamiliar).


Help with figuring out if MAX(L) is a CF language

Let $L = a^*b^*c^* \setminus \{ a^n b^n c^k : k > n \}$. To see that $L$ is context-free, note that we can write it as follows:
$$
L = \{ a^n b^m c^k : n > m \} \cup \{ a^n b^m c^k : m > n \} \cup \{ a^n b^m c^k : k \leq n \}.
$$
The only way in which a word in $L$ cannot be extended non-trivially into another word in $L$ is if the word is of the form $a^nb^nc^n$ for $n \geq 1$. Therefore
$$
\mathrm{MAX}(L) = \{ a^n b^n c^n : n \geq 1 \},
$$
which is known to be non-context-free.


In control flow graphs, what is the difference between a path and a branch?

I do not know the exact definitions used by your class, so I am saying this with caution. A branch normally correspnds to a graph edge that allows control to pass from one node to another in the graph. A path is a succession of edges connected to each other, with possible repetition and representing the successive parts traversed by the control. So a branch will be a element of the program structure, a static entity. The path represent a fragment of computation.

If you say more about what you understood, I may be able to tell you whether it makes sense.


Examples of context-free languages with a non-context-free complements

The language $L_1= \{ww \mid w \in \{a,b\}^*\}$ is not context-free (as can be shown using the pumping lemma; see here).  Its complement $L_2 = \{a,b\}^* \setminus L_1$ is context-free (as shown here).  This gives a simple and elegant example of a context-free language (over a binary alphabet) whose complement is not context-free, as you requested.