Is object oriented programming considered to be a declarative programming approach?

When you write an OO code, you describe object features (attributes, properties, methods) and implement them. This may be seen as declarative: you do not have an imperative approach giving the sequence of operations to reach a given goal; you have a declarative approach describing features of objects, in a sense characterizing them.
To be more precise, let me take an example. When one says that an image has a filtered version, a blurred version, etc, this may be seen as declarative; these are features of any image. When one implements a procedure to filter or blur an image, then this is imperative: the code is thought of as a sequence of operations aiming at transforming an image, not a description of what the transformed image is.
I am not an expert, though, so I hope someone will correct this if needed.


How to draw a clearly arranged DFA of a language with modulo rules?

Here is the minimal DFA. It keeps track of $|w|_a-|w|_b+2|w|_c\bmod 5$.


Proving by induction that a function gets called n-1 times

Here, I'm going to let $n = L-f$ and let $M(f,L)$ be the number of times min is invoked when calling $Foo(A,f,l)$. Notice when $n=0$, then $L=f$ and clearly Foo invokes the function min $0$ times so the condition is satisfied.

Now suppose that the assertion is satisfied for $n \leq k$. We want to show it holds true for $n=k+1$, i.e., suppose that $L-f = k+1$. Since $Foo(A,f,L)$ has to invoke min once and then invoke it as many times as its invoked in the recursive calls, we get that,

$$M(f,L) = 1 + M(f,m)+M(m+1,L).$$

Now notice that for $M(f,m)$ and $M(m+1,L)$, the quantity $m-f$ and $L-(m+1)$ are both less than $L-f = k+1$ (since $m$ is essentially the midpoint of $L$ and $f$). So by the inductive hypothesis $Foo(A,f,m)$ invokes min at most $m-f-1$ times and $Foo(A,m+1,L)$ invokes min at most $L-(m+1)-1$ times. Plugging these into our equation yields, we get,

$$M(f,L) = 1 + M(f,m)+M(m+1,L) \leq 1 + (m-f-1) + (L-(m+1)-1) = L-f-1 = n-1,$$

as desired.


The standard definition of DFA (as well as NFA) allows the set of accepting states to be empty. Indeed, otherwise the Myhill–Nerode theorem would be false. The theorem states that the number of states in a minimal DFA for $L$ equals the number of equivalence classes in the Myhill–Nerode relation for $L$. When $L = \emptyset$, this relation contains one equivalence class (consisting of all strings), and so there should be a DFA for $L$ having a single state.

Of course, you can define DFAs in any way you like, and in particular, your teacher's definition still results in the same class of regular languages. Nevertheless, the standard definition is better, for the reason stated above.


Think of it the other way around.
If you duplicate an image then you get zeros in between the transform (
This can intuitively be explained:
duplicating an image is like convolving with 2 deltas (comb) of wavelength 1/2 the new image size. so is equivalent under convolution theorem to multiplying with comb of freq size of image / 2 which gives a comb with delta every other pixel -> every other pixel is zero.


Travelling Salesman Problem with Memoization

In the 3rd if statement your code assumes that the optimal solution when starting from coordinates $(m, n)$ is equal to the optimal solution when starting from coordinates $(n, m)$. This is clearly false in general.


How would one prove the pigeonhole principle with a SAT solver?

SAT solvers work in the propositional calculus, and usually accept as input a formula in conjunctive normal form. There are several different propositional variants of the pigeonhole principle; they are all contradictions, and the actual pigeonhole principle is their negation. One of them, which states that there is a one-to-one mapping from $\{1,\ldots,n\}$ to $\{1,\ldots,n-1\}$, is described in page 2 of this book extract (apparently Jukna's Extremal Combinatorics), where you can also find an exponential lower bound for refuting the pigeonhole principle in the resolution proof system.

(Reiterating, to prove that there is no one-to-one mapping from $\{1,\ldots,n\}$ to $\{1,\ldots,n-1\}$, we instead refute the formula stating that such a mapping does exist.)

SAT solvers are (almost) all based on the DPLL procedure (with some hacks such as clause learning), and so when they refute a statement, their transcript can be converted to a resolution refutation. Therefore the lower bound mentioned above shows that SAT solvers will have a hard time refuting the pigeonhole principle.


Why is a regular language called 'regular'?

As Kaveh says in a comment, Kleene bestowed the name way back when he kicked off automata theory and formal languages. I believe the term was arbitrary, though it has been many years since I read his original paper.

Mathematicians have a habit of hijacking common nouns and adjectives for mathematical objects and properties, sometimes with good reasons such as geometric or other analogies or metaphors, and sometimes arbitrarily. Just look at "group", "ring", "space", "sheaf", "atlas", "manifold", "field" and so on.

In fact, the term "regular" for finite-state languages, while still prevalent in automata theory, is not used very much in its algebraic cousin, finite semigroup theory or abstract algebra in general. Why? Because the term was already taken for a semigroup that is close to a group in a specific technical sense, so you couldn't match up a regular language in Kleene's sense with a corresponding regular semigroup. Third, Kleene defined another kind of event called "definite", which was much studied for a while, but has turned out to be not particularly fruitful. Today, finite sets of language play the role of definite events as the basis for regular events.

The preferred term in algebra is "rational" for both Kleene's class of languages and the more general semigroups and monoids. That usage also reflects an important analogy between the term "rational" in algebra as the solution of a linear equation with integer coefficients and the concept of rational power series in automata and formal language theory.

Additional information.  Kleene's original paper of 1951, entitled "Representation of events in nerve nets and finite automata" may be found here. On p. 46 it settles the arbitrariness of the term "regular" with this statement:

  We shall presently describe a class of events which we will call "regular events".  (We would welcome any suggestions as to a more descriptive term.)

Apparently, nobody came up with a more descriptive term. ;-)

As is often the case with seminal papers which lead to the intensive development of whole new areas, the terminology and concepts are almost unrecognizable in today's terms. First, the paper was about models of neurons, hence the use of "events" instead of "languages" or "sets". The term "events" persisted well into the 60's and 70's, even after the importance of Kleene's concepts for automata and formal languages vastly outweighed any value for neuroscience.

Second, there are some mathematical differences, such as defining what came to be called "Kleene Closure" as a binary operation, equivalent to $a^*b$, instead of the simpler unary operation $a^*$ or $a^+$ that we use today. Kleene's motivation was to avoid the empty string (or event with duration zero in his terms). That was a remarkably prescient intuition since subsequent theory has shown how crucial the choice is to include or exclude the empty string from definitions in many contexts. Third, Kleene defined a concept called "definite events" and developed regular events from them, but nowadays we use finite sets for the purpose. Definite events were studied for a while, but have turned out to be far less important than regular events/sets/languages.

Anyway, a complete reading of this paper is probably not worth anyone's time today, except for historical purposes. I just skimmed it for the crucial definitions and ideas, and that was fun.


Proving Linear Time Temporal Logic formula □ ◊ f ⇔ ◊ □ f

You are not missing anything. These expressions are indeed not equivalent.
Assume $f$ in your case is an atomic proposition. Then the computation:
$f,\neg f,(f,\neg f)^\omega$ satisfies $□◊f$, but not $\Diamond \square f$.

Intuitively, $\Diamond \square f$ means "After a finite prefix, there is always $f$", while $\square \Diamond f$ means: "There are infinitely many $f$s".

By the way, you have some mistake in your semantics. It should be:
$(\sigma,j)\models \Diamond f$: $\exists k[k\ge j\wedge (\sigma,k)\models f]$.


Perform the following 8-bit two's complement arithmetic operation

Two's complement is a way of representing positive and negative numbers in binary.  There is a very good explanation here: https://stackoverflow.com/questions/1049722/what-is-2s-complement

Basically, the really clever part about two's complement is that arithmetic works without making any special changes.  Let's look at that in action with n addition operation: $10000001 + 00010000 = 10010001$.  Notice that no special actions were taken in finding the sum.  Nevertheless, what I've written there is that $-127 + 16 = -111$.

Two's complement is really just a clever way of encoding the numbers designed to make arithmetic straightforward.

By the way, an easy way of reading two's complement numbers is just to reverse the sign on the highest bit.  To illustrate what I mean by this, regularly encoded (non-complement) 8-bit integers like $10010011$ and $01000010$ could be found by adding $1 + 2 + 16 + 128 = 147$, and $2 + 64 = 66$ respectively.

If we were to designate these same numbers as two's-complement, we would just reverse the sign on the 128s bit.  Now our two numbers would be  $1 + 2 + 16 -128 = -109$, and $2 + 64 = 66$.  The second number didn't change because the highest bit was a $0$ already, so it doesn't matter if we are adding or subtracting it.

So, if you were to try to subtract $01110000−11101011$, let's get an answer first so that we can check ourselves.  $64+32+16 = 112$, and $-128+64+32+8+2+1 = -21$.  You are performing the subtraction $112 - -21$.  This means that our final answer should be $133$.

So, just as you can subtract by negating before you add (ie. $112 + 21$ instead of $112 - -21$), we can perform a similar operation here.  If we negate the second number, we flip the bits and add one: $00010100 + 1 = 00010101$.  But now that we've negated the number, our subtraction has become an addition problem.  So, our original $01110000−11101011$ has become $01110000 + 00010101$

  01110000
+ 00010101
  --------
  10000101

$10000101$ is $-128 + 4 + 1$, which equals...

$-123$.

-123?? Wait, what happened?

We've fallen into the classic two's complement trap!  Because we only have 8 bits, we only have a limited range of possible numbers.  8 bits allows for 256 possible values.  Two's complement divides these values nicely: half are positive and half are negative, giving us a range of $-128$ to $127$.  Why one less in the positives?  It's because Zero has to be somewhere, and since $00000000$ doesn't start with a leading $1$, it comes out of the positive space.

If you're just doing pure math, simply add an extra digit, and you'll be out of trouble.  $010000101$ is $128 + 4 + 1$, which equals $133$. If you're on a computer, however, you have to pay more attention to this problem.

When you go outside of the range of your bits, you are said to have an overflow error.  Modern processors and languages have evolved ways of dealing with this problem, typically through flagging operations that might have caused overflow.


Do we need regular expression first or finite state automata in lexical anlysing?

A regular expression is a language used to describe a finite state automaton. It allows you to define the fsa without drawing nodes and edges all over the place. The two go hand in hand in that regard.


Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output

I do not know about their algorithm, but the problem is easy to solve in $\mathcal{O}(V \cdot e)$ time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this takes $\mathcal{O}(E)$ time, but we can use the irreducible kernel we have already built to do it in $\mathcal{O}(e)$ time.

First note that $e \geq n-1$ if the graph is connected. If it is not, solve the connected components individually.

Start by doing topological sort on the vertices, with vertices with indegree zero first. Loop vertices first-to-last. When at vertex $i$, first mark all vertices as unreachable. Then loop vertices from $i-1$ to $1$. At every vertex $j$, if $j$ is unreachable and has an edge to $i$ in the input graph, add the edge $(j, i)$ to the irreducible kernel and mark $j$ reachable. Then if $j$ is reachable, loop all edges $(t, j)$ in our kernel, and mark $t$ reachable.

The topological sort takes $\mathcal{O}(V + E)$ time, and the DFS takes $\mathcal{O}(E + V \cdot e)$ time, so since $e = \mathcal{\Omega}(V)$, the running time is $\mathcal{O}(V \cdot e)$.

The produced DAG has the same reachability as the original graph, as we use a subset of the original edges, and only skip adding the edge $(j, i)$ if $i$ is reachable from $j$ even without it.

Assume some edge $(j, i)$ can be deleted while maintaining reachability. But by the way we did the DFS, $i$ was not reachable from $j$ without the edge (note that any path between them can only visit vertices between them in the topological order). Hence the produced DAG is indeed irreducible.


You haven't really asked any question, but it seems like you don't know what $\rm{P}^A$ means and what $\rm{NP}^A$ means for a language $A$.  The class $\rm{NP}^A$ is simply all languages that are decidable in "NP time", given a turing machine with $A$ as an oracle.  This means a non-deterministic turing machine with access to $A$ which runs in polynomial time.  The $\rm{P}^A$ is the deterministic version.


In the Traveling Salesperson Problem, is the shortest tour the same regardless of the start/return city? How do you prove it?

The optimal tour visits all vertices so it's still a tour regardless of where you start. The length of the tour is the sum of the lengths of its edges. Addition is commutative and associative so it doesn't matter what order you do the addition.


When to terminate search for path in an infinite grid

Unfortunately, the simple answer is, you can't.

All the standard search algorithms have a runtime that's polynomial in the size of the graph. If your graph is infinitely large, there's no guarantee that they'll ever terminate for arbitrary inputs: how can they ever know whether they should give up now, or whether they'd find the answer if they just expanded one more node?

Any approach that involves putting an upper limit on the number of steps, is doomed to failure. Even if the start and end points are right next to each other in the coordinate system, I could delete the edge between them, then make it so that the shortest path from one to the other takes one more step than you're allowing. And then your algorithm will say, incorrectly, that there's no solution.

However, if you have additional information about your graph (perhaps there's only a finite number of edges missing from the grid?), then you can potentially exploit this to find an answer. It's only impossible for arbitrary infinite graphs; there are many classes of infinite graphs for which it can be solved.


Asymptotic time complexity for finding maximum element in an array

The usual model of computation used to analyze algorithms is the unit-cost RAM model, in which machine words have width $O(\log n)$, and operations on machine words (including dereferencing) take constant time.

In this model of computation, you can find the maximum of an array of length $n$ words in linear time.


Decidablity with exponential number of solution

If a problem has a finite number of possible solutions, then you can enumerate all the potential solutions, and if one of them is correct, halt. Otherwise, halt and reject after checking the last solution.

It does not matter how long this process takes, it may be exponential, or superexponential as in your example of $2^{2^n}$, the only thing that matters is that there is a way to enumerate all candidate solutions.


Find the loop invariant of the given while loop

At the end of each iteration you have
$$
\forall j: 0 \leq j < i \implies b[j] = a[j+1]
$$
which you can prove by induction. Thus, when the algorithm terminates, $i$ has reached $n-1$ and you have
$$
\forall j: 0 \leq j < n-1 \implies b[j] = a[j+1]\,.
$$

I figured this out by just asking myself what kind of statement I can make at the end of each iteration. In this case it's that the first $i$ elements have been copied. Then I just turned that into a formal statement.


How to prove the performance, Big Omega ,of building a binary heap using recursive method is Ω(nlog(n))

Suppose that your heap is a max-heap: a parent should be larger than its children. Consider what happens when you call buildheap with the numbers $1,\ldots,n$ in that order. Each time you add a new element to the bottom level of the heap, and the heapify procedure diffuses it all the way to the root. Since element $k$ is put at level $\Theta(\log k)$, inserting the $k$'th element takes time $\Theta(\log k)$. Overall, buildheap takes time $\Theta(\log 1 + \cdots + \log n) = \Theta(\log n!) = \Theta(n\log n)$.


NP completeness of deciding whether a set of examples, consisting of strings and states, has a corresponding DFA?

(Note: the below proof may have some issues raised in the comments. I am in the processing of addressing the issues.)
The following "end-character" method was suggested in the comment above, as well as private communication with some others. Any mistakes are my own.
We construct a polynomial-time reduction from the Gold problem (arbitrary alphabet with "accept" or "reject" in the examples) to the Sipser problem (binary alphabet with states in the examples). Since the Gold problem is NP-complete, it then follows that the Sipser problem is also NP-complete.
The Gold decision problem gives us an integer $n$ and pairs $(s_1, x_1), (s_2, x_2) \ldots (s_k, x_k)$ [where each $s_i$ is a string in some arbitrary alphabet $\Sigma$, and each $x_i$ is either "accept" or "reject"] and asks if there exists an $n$-state DFA $G$ that for each $i$, accepts or rejects $s_i$ based on the value of $x_i$.
We claim that the Gold input has such an $n$-state DFA if and only if the examples $(t_1, y_1) \ldots (t_k, y_k)$ has a corresponding $f(n)$-state DFA $H^\prime$ in the Sipser problem, where:

$t_i$ is some binary encoding of $s_i$ plus a common suffix $Z$ that is unambiguously different from any of the other encoded characters in $\Sigma$.
$y_i = q_{x_i}$; that is, either $q_\mathrm{accept}$ or $q_\mathrm{reject}$
$f(n)$ is a function that be computed and written down in time polynomial in $\log n$.

First, suppose the Gold DFA $G$ exists. Then, there exists a size $O(n \log \lvert \Sigma \rvert)$ DFA $H$ that recognizes the homomorphism ($\Sigma$ encoded into binary) of the language of $G$: simply take every transition in $G$ and split up into transitions corresponding to the binary encoding. Since $G$ may have more than one accept state, so does $H$ (which has the same number of accept states as $G$). Hence, modify $H$ by taking every accept state and inserting transitions corresponding to the "end of string" bitstring $Z$ to a single newly-created $q_\mathrm{accept}$, and inserting the same transitions from non-accept states in $H$ to a single newly-created $q_\mathrm{reject}$. The resulting DFA $H^\prime$ clearly fits the examples $(t_i, y_i)$, and its number of states is bounded above by some easily computed $f(n)$.
Now for the other direction, suppose some $f(n)$-state DFA $H^\prime$ exists which fits the examples $(t_i, y_i)$. Then, since by construction every $t_i$ has the "end of string" bitstring $Z$ as a suffix, we simply take $H^\prime$ and for every state $q$ for which reading $Z$ would take $H^\prime$ to $q_\mathrm{accept}$, we make $q$ an accept state. Then, we remove $q_\mathrm{accept}$ and $q_\mathrm{reject}$, and we have the DFA $H$. We can then construct a DFA $G$ which recognizes the same language with characters decoded from binary to alphabet $\Sigma$. This construction can easily be done by starting with the start state in $G$, trying out every encoded character in $\Sigma$ and writing down the transitions in $G$, and recursively repeating. Since $H$ is finite, this procedure is guaranteed to terminate in polynomial time.
(Note: the above solution simply quotes the Gold result, the proof of which is pretty involved. There's probably a simpler method that directly proves the Sipser result instead of using Gold as an intermediary.)


I want a fast rank only shuffling algorithm for a full 52 card deck

I'm pretty sure there's no way to take any significant advantage of the fact that you don't care about the suits.  The most effective solution is likely to just generate random permutations of the integers from 0 to 51, and map these to card ranks by dividing by 4 and rounding down (which can be done with a simple bit shift, since 4 is a power of 2).

As Apass.Jack notes in their answer, for generating the permutations you almost certainly want to use some form of the Fisher–Yates–Durstenfeld–Knuth shuffle, since it avoids the inefficiency of the sample-and-reject-duplicates method when only a few valid choices remain.  Since you're generating permutations of consecutive integers, you may want to consider using the "inside-out" variant of the shuffle (probably first described by Knuth in 1994):

for i from 0 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← i

The main advantage of this algorithm over the "standard" FYDK shuffle is that you don't need to initialize the results array a before shuffling it, since it gets dynamically initialized during the shuffle.

Nonetheless, you may want to implement both a standard FYDK shuffle and the inside-out variant and benchmark them, since their different memory access patterns can affect real-world performance in ways that are hard to predict in advance.

In any case, at this point the biggest remaining opportunities for optimization are likely to be:

using random numbers more efficiently,
using a faster random number generator, and
switching to a lower-level language.

Of these three, I'd actually recommend starting with #3; this is exactly the kind of problem where using a low-level compiled language like C or C++ (or even a mid-level language with a good JIT compiler, like Java) can provide significant performance benefits with relatively little cost in development effort.

Once you've ported your code to a low-level language, you may want to consider optimizing your choice of RNG.  There are some pretty fast PRNGs out there (my personal favorite being Bob Jenkins' "flea" RNG, as reviewed e.g. here), but to properly realize their benefits, you need to also minimize the overhead cost of calling the generator (ideally, letting your compiler inline the PRNG code directly into your shuffling loop).

Finally, it's worth noting that most PRNGs generate something like 32 or more bits of (pseudo)randomness per call, whereas a Fisher-Yates shuffle of a 52 card deck only uses less than 6 bits per iteration.  Thus, there could certainly be room for optimization by splitting RNG outputs into smaller pieces and reusing them for multiple iterations of the shuffling loop.

That said, I'd personally rather avoid this option, at least until I had exhausted all other possible avenues for optimization.  One problem is that, even if your RNG provides perfectly random outputs, it's easy to introduce subtle bugs in the splitting process that can bias your results in ways that may not be so easy to detect.  Another problem is that trying to squeeze every last drop of entropy out of your (P)RNG output is a good way to magnify any non-random biases that output may have.  Personally, I would feel safer using a fast but possibly not quite perfect PRNG to generate lots of extra random bits, and converting them to random numbers in the required range in a simple and relatively foolproof way, than trying to use up every last bit of my RNG output and relying on that RNG and my conversion code having no subtle weaknesses.

Still, there are some simple optimizations you can safely make here.  For example, you can trivially save one RNG call (and some other unnecessary work) per shuffle by modifying the code above to look like this:

a[0] ← 0
for i from 1 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← i

The only difference between this code and the version I copied from Wikipedia above is that I skipped the first iteration, where we always had i = j = 0, and instead just initialized a[0] before the loop.  While such little optimizations won't have much effect alone, they're pretty easy and safe and can add up.

In fact, since you said don't care about the card suits, I guess we can save a few more RNG calls:

for i from 0 to 3 do
    a[i] ← 0
for i from 4 to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i
        a[i] ← a[j]
    a[j] ← ⌊i / 4⌋

This generates the card ranks directly, by doing the division by 4 inside the initialize-and-shuffle loop, and splits the first four iterations of that loop (where all elements of the array are still identical) into a separate loop.  This way, you'll only need 48 RNG calls to shuffle 52 cards.  That's almost an 8% speedup (assuming that random number generation dominates the time cost), which might be significant just by itself.

Ps. FWIW, while precalculating the shuffled decks and storing them on disk is certainly an option worth considering, I very much doubt it is optimal.  With a fast shuffle and a fast RNG, both implemented in a low-level language, shuffling the decks dynamically should be orders of magnitude faster than reading them from even a very fast solid-state disk.

Addendum: There's a potential advantage to reshuffling your previously shuffled decks, rather than generating a new deck for each shuffle: it can smooth out possible biases in your shuffling process and give you a more uniform distribution of shuffles.

Basically, if you start with a new in-order deck for each shuffle (or generate one during the shuffle, like the code above does), then you're repeatedly sampling decks from the same distribution.  If your RNG (or the way you convert its output into array indices) is not perfect, then this distribution may be biased.

In particular, if you're using a PRNG with less than $\log_2(52!) \approx 225.6$ bits of internal state, then you're guaranteed to have some decks that you can never generate by shuffling an in-order deck, simply because there will be more possible decks than there are possible initial states for your PRNG at the beginning of the shuffle.  If you don't care about the suits, the corresponding threshold drops to $\log_2(52! \mathbin/ 4!^{13}) \approx 166$ bits.  But of course, in either case, you'd need at least twice as many bits just to be reasonably sure that all possible decks can be generated, and even more to guarantee a reasonable level of uniformity.

On the other hand, if you keep reshuffling a previously shuffled deck, then you're effectively performing a (pseudo)random walk on the set of possible permutations, with the possible transitions defined by the relation "$A$ can be shuffled into $B$ by the PRNG".  As long as this random walk is ergodic (and it should usually be, even for pretty crappy RNGs), it should converge towards a uniform distribution on the set of all possible permutations (since the transition kernel is also invariant with respect to the semigroup action).

Thus, if you could keep shuffling the same deck over and over, even with a poor-quality PRNG, you should in principle have a pretty high chance of eventually encountering each possible shuffle equally often.  Of course, the order in which you'd encounter these shuffles might not be fully random, and (if you never reseeded the PRNG from a truly random source) there would still be a small probability of getting caught in a short cycle that visits only some of the possible shuffles.  And of course, with a 52 card deck (with or without suits), you'd never actually be able to test this within your lifetime on any computer you could possibly build.

But still, in general, a good rule of thumb is that reshuffling the same deck over and over will tend to smooth out any possible biases in the shuffling process, compared to starting from an unshuffled deck each time.  In fact, that's pretty much the reason why the often rather imperfect shuffling done by humans using a physical deck of cards is still sufficient to avoid generating noticeably biased decks, and why card players are advised to be extra careful in shuffling a new deck before using it for the first time.

Fortunately, both the standard Fisher-Yates shuffle and the inside-out version described above can be easily made to reshuffle an existing deck.  In fact, the standard version does that by default, while for the inside-out variant the changes are minor.  Specifically, assuming that a is already a (possibly shuffled) permutation of n cards, either of the following loops will serve to reshuffle it:

// standard FYDK shuffle (descending order)
for i from n - 1 down to 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i: swap a[i] and a[j]

// "inside-out" version (Knuth 1994)
for i from 1 up to n − 1 do
    j ← random integer such that 0 ≤ j ≤ i
    if j ≠ i: swap a[i] and a[j]

Either of these will require $n-1$ RNG calls to (re)shuffle an $n$ card deck; unfortunately, in this case, I really don't see any practical way to save any more RNG calls even if some of the cards in the deck are known to be equivalent.

Addendum 2: If your language / CPU can do fast 256-bit math (specifically, division and remainder), and you have access to a high-quality RNG than can generate 256-bit numbers quickly (such as using two calls to AES_CTR_DRBG, which should be pretty fast on x86 CPUs that support the AES-NI instruction set, if your crypto library makes use of it), then you could do something like this:

r ← random 256-bit integer (i.e. 0 ≤ r < 2^256)

// optional bias elimination via rejection sampling
while r < 2^256 mod 52!
    r ← random 256-bit integer (i.e. 0 ≤ r < 2^256)

// inside-out FYDK shuffle-and-initialize
a[0] ← 0
for i from 1 to 51 do
    j ← r mod (i + 1)
    r ← ⌊r / (i + 1)⌋
    if j ≠ i: a[i] ← a[j]
    a[j] ← i

where hopefully either your compiler is smart enough to fuse the modular reduction and division of r by i + 1 into a single operation, or your language directly provides a combined "divmod" operator or function for it.

As noted in the comments above, the bias elimination by rejection sampling is not strictly required; omitting it just means that about 30% of all possible shuffles are very slightly more likely (about $1 + \frac{52!}{2^{256}} \approx 1.0000000007$ times as likely, to be exact) to occur than the rest.  It's up to you to decide whether that bias is something you're willing to accept.  If you do decide to use the bias elimination, do precalculate the constant 2^256 mod 52!, as calculating it from scratch is likely to be almost as expensive as the shuffle itself.

If you don't have access to efficient 256-bit math, you can always split the shuffling loop into smaller pieces.  For example, $20!$, $32!\mathbin/20!$, $43!\mathbin/32!$ and $52!\mathbin/43!$ are all less than $2^{64}$, so using 64-bit math you could do something like this:

s ← 1
a[0] ← 0
for t in (20, 32, 43, 52) do
    m ← 2^64 mod (t! / s!)
    r ← random integer such that m ≤ r < 2^64
    for i from s to t - 1 do
        j ← r mod (i + 1)
        r ← ⌊r / (i + 1)⌋
        if j ≠ i: a[i] ← a[j]
        a[j] ← i
    s ← t

where I'm assuming that the code used to generate a random integer such that m ≤ r < 2^64 internally consumes 64-bit random numbers and does any rejection sampling needed to ensure that the fall into the desired range.  Of course, in practice you'd probably want to unroll the outer loop and to precalculate the m values for each iteration, or at least to store them in a look-up table.

If you're limited to 32-bit math (or, in particular, if you only have a 64 → 32 + 32 bit divmod operation), you can instead iterate over t in (12, 19, 25, 30, 35, 40, 44, 48, 52) and set m to 2^32 mod (t! / s!).  Note that this requires nine iterations of the outer loop instead of eight, since there will be some unused entropy left in r at the end of each iteration.  In principle we could recycle this entropy, but that would complicate the code even more, so I'll leave that as an exercise. ;-)

In any case, whichever method you choose, you will definitely want to test your code very throughly before using it.  I have not done so myself for the pseudocode examples above, so they might contain bugs, and porting them from pseudocode to your actual programming language could easily introduce more.

Unfortunately, shuffling is exactly the kind of task where it's very easy to make subtle mistakes that are hard to catch in testing due to the inherent stochasticity of the task.  Some useful tests I'd recommend include:

shuffling a small deck of, say, 3 to 5 cards many times, and checking that each possible shuffle occurs approximately equally often (e.g. using Pearson's $\chi^2$ test);
shuffling a full 52 card deck many times (starting with an ordered deck each time, to maximize any observable bias), recording the position of some specific card in the deck, and checking that those positions are approximately uniformly distributed (again using e.g. a $\chi^2$ test; repeat this for each of the 52 cards);
same as above, but instead recording the distribution of cards occurring in a given position in the shuffled deck;
same as the two tests above, but instead record the difference in the positions of two specific cards (modulo 52) or the difference in the card values at two specific positions in the shuffled deck (note that in both cases there will be 51 possible differences, since 0 is not a possible result);
same as above, but instead of just recording the difference, record each observed pair of positions or card values (note that you'll need more shuffles per test for this, since there will now be 52 × 51 possible outcomes);
count the number of disjoint cycles in the permutation generated by the shuffle, and check that the distribution of this count over many shuffles matches the expected distribution given by the Stirling numbers of the first kind (in particular, this test should catch any off-by-one errors leading to an accidental implementation of Sattolo's algorithm instead of the standard FYDK shuffle);
other statistical randomness tests, especially any tests that would directly measure some specific property that you both care about in your actual simulation and can predict the theoretically expected distribution of.


Finding the lexicographically smallest palindrome of the same length that is lexicographically greater than or equal to given string s

Let's assume the length is even for now. Split the word up into two equal parts, $w = lr$. Let $l^R$ be the reverse of $l$.
If $l^R = r$, we are done immediately. Otherwise, if $r < l^{R}$ we can set $r$ equal to $l^R$. The more involved case is when $l^R < r$. In that case we will need to increment $l$ by one (view the lowercase English words as a base-26 number - this exactly matches lexicographic order), after which we can set $r$ equal to the reversed left hand side and we'll still be lexicographically bigger.
Now if our original word was odd in length we apply the exact same process, except when we shouldn't increment $l$ by one but start the increment one more to the right: at the middle element instead.
Some example code in C:
void increment_base26(char* s, int len) {
    int i = len - 1;
    while (i >= 0) {
        if (s[i] == 'z') s[i] = 'a'; // Wrap around and carry.
        else { s[i] += 1; break; }
        i -= 1;
    }
}

void reverse(char *s, int len) {
    for (int i = 0; i < len - 1 - i; ++i) {
        char t = s[i];
        s[i] = s[len - 1 - i];
        s[len - 1 - i] = t;
    }
}

void next_lexicographic_palindrome(char* s) {
    int len = strlen(s);
    int half = len / 2; // Rounds down.
    int half_plus_mid = half + (len % 2);
    reverse(s, half);                                // Compute l^R.
    int cmp = strncmp(s, s + half_plus_mid, half);   // Compare l^R and r.
    if (cmp > 0) memcpy(s + half_plus_mid, s, half); // l^R > r, can just copy over l^R.
    reverse(s, half);                                // Undo l^R -> l.
    if (cmp >= 0) { return; }                        // Simple cases l^R >= handled.
    increment_base26(s, half_plus_mid);              // Increment left + mid.
    reverse(s, half);                                // Copy over the new l^R to r.
    memcpy(s + half_plus_mid, s, half);
    reverse(s, half);
}


Proving that $A \vee (\neg A \wedge B) \equiv A \vee B$

Note that

$\qquad A \lor (B \land C) \equiv (A \lor B) \land (A \lor C)$;

you can "multiply out". Add in

$\qquad (A \lor \lnot A) \land B \equiv B$

and you are done.


Can't Understand this Subset Construction Proof

Since any of $2^n$ subsets of the last $n$ symbols could have been $1$, ...

This is just referring to the fact that there are $2^n$ possible sequences of length $n$ made up of $0$'s and $1$'s. That is, if you have $n$ symbols, you can think of "a subset of those symbols being $1$" as taking a subset of the indices from 1 to $n$ and making the symbols at those indices be $1$.

  If $i>1$, then consider the state $p$ that D enters after reading $(i−1)$ $0$'s. Then $p$ must be both accepting and nonaccepting, since $a_ia_{i+1}\ldots a_n00 \ldots 0$ is accepted and $b_ib_{i+1}\ldots b_n00 \ldots 0$ is not.

So you have two sequences of characters $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$ which end up in the same state. You know that $a_i=1$ and $b_i=0$. Now take both of those strings and append $(i-1)$ $0$'s to each one. This gives you the following two strings $x$ and $y$:

$x= a_1a_2\ldots a_i\underbrace{a_{i+1}\ldots a_n}_{n-i\text{ symbols}}\underbrace{00 \ldots 0}_{i-1\text{ zeros}}$

which we know is a string such that the $n$th symbol from the end is $1$ ($a_i = 1$ and it is the $n$th symbol from the end).

$y= b_1b_2\ldots b_i\underbrace{b_{i+1}\ldots b_n}_{n-i\text{ symbols}}\underbrace{00 \ldots 0}_{i-1\text{ zeros}}$

which we know is a string such that the $n$th symbol from the end is $0$ ($b_i = 0$ and it is the $n$th symbol from the end).

Now think about what happens when you run these two strings through D. It's actually quite similar to the $i=1$ case: since the two strings ended up in the same state $q$ after reading $a_1a_2\ldots a_n$ and $b_1b_2\ldots b_n$, they also have to end up in the same state $p$ after reading $(i-1)$ more $0$'s. Thus this state $p$ has to be both accepting and nonaccepting since our string $x$ should be accepted but $y$ should not be accepted.


Your outcomes are not the number of candidates but rather which candidates were hired: $\Omega = \{0,1\}^n$. Then you have $X_i(a_1, \dots, a_n) = a_i$ and $X(a_1, \dots, a_n) = \sum\limits_{i=1}^n X_i(a_1, \dots, a_n) = \sum\limits_{i=1}^n a_i$.


Understanding Alpha Beta Pruning: Why do we ignore the values of a unsearched tree after the first leaf, can they not include acceptable values too?

At $d)$, minimizer is comparing the $2$ he found with the currently best option for the maximizer higher in the tree (at node $A$, where maximizer will choose between $B$,$C$,...), which is $3$, at node $B$. He then knows that maximizer will not choose $C$.

The node $C$ will have value $2$ when minimizer sets it and would have value $2$ or less if minimizer explored it fully, so he doesn't need to waste his time searching other branches from $C$ if he already knows that maximizer will not choose anything lower than $3$.

I think what confuses you may be the following:
You are imagining a real-life gameplay scenario, but this is different in the sense that minimizer and maximizer must play their best move and will calculate it correctly.
So there is no way that minimizer could in this situation "fool" maximizer by setting the wrong value of $C$ (something higher than $3$) to force maximizer to choose it. If we assume that scenario a possibility, we must also implement the maximizer with "free-will" so he may not choose his best option but this is no longer an $\alpha$-$\beta$ pruning :)


$\mathsf{PSPACE}$ membership in exponentially many steps?

whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

Yes, of course. Polynomial space means exactly what it says.

The only reason you should worry is if you think that your algorithm takes more time than $2^{n^c}$ for all $c$.  In that case, it must either use more than polynomial space or loop forever since, there are only $|\Sigma|^{n^k}$ configurations of a tape of length $n^c$ using alphabet $\Sigma$, only $n^k$ possible head positions and only a constant number of possible states. That means there are only $|Q|n^k|\Sigma|^{n^k} \leq 2^{n^c}$ (for large enough $c$) possible configurations for a polynomial space Turing machine so if it runs for more than that many steps, it must have seen the same configuration twice so it must be in an infinite loop.


How to construct a DFA which accepts all the strings endig with aa and no two consecutive b (bb)

If you know how to construct DFAs for two languages separately, you can use systematic methods to build the DFA which recognises the intersection of the languages (e.g. https://math.stackexchange.com/questions/147457/intersection-of-two-deterministic-finite-automata). However to achieve a minimalist and elegant result (as well as for learning purposes) you may want to try and find ad-hoc methods.
NB: You can always apply a DFA minimization procedure to 'clean up' the automaton obtained via the above general method (https://en.m.wikipedia.org/wiki/DFA_minimization).


Is it possible to add every word in a file to a set in $\mathrm{O}(n)$ time?

Splitting

While splitting you have to touch every element once to see that is a delimiter or not. So it $\in \mathcal{O}(n)$

Assuming a Hash-based Map is used;

  cost of Inserting a string

It is $\in \mathcal{O}(1)$ but if you consider the hash function as not a constant then you have to analyze the hash function itself. When we are talking a hashmap, the string size, usually, is not considered.

  Total insert cost

It is $\in \mathcal{O}(n)$,

  Total cost

It is the sum of all = $ \mathcal{O}(n) + \mathcal{O}(n)= \mathcal{O}(n)$


There are two parameters to DBSCAN: minPts, and ε.
You have an outlier point if there are fewer than minPts points within ε of it (using the appropriate distance metric). If this isn't the case, it's a sufficiently dense region that there is a cluster here.


What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?

Given an integer k, are there integers (positive or negative) x, y, z with an absolute value ≤ $10^{1000}$ such that $x^3 + y^3 + z^3 = k$?

It is believed that without the limit on the absolute values the answer is "Yes" unless $k \equiv 4 \mod 9$ or $k \equiv 5 \mod 9$. On the other hand, solutions are so rare that most likely solutions for some values k cannot be found in the lifetime of the universe.

And both the inputs, and the space needed for a computation, are tiny. The limitation on the size of x, y, z makes it decidable.


Can algorithm discovery be brute forced?

You are correct in saying that algorithms are no more than a sequence of strings. However, you should make the distinction between syntactic and semantic properties of the algorithm. Syntactic properties are those relating to the actual code, e.g. what is the length of the program? how many "while" loops does it contain? Semantic properties are related to what the program actually does, e.g. is there some input that would cause this program to go into an infinite loop?

The problem you encounter in your suggestion is that almost every interesting semantic property is undecidable, meaning that even with unlimited resources (time/memory) you cannot algorithmically reason about this property just by looking at the source code.
So in fact, the situation is worse than what you think. Even the craziest hardware won't help us, since such tasks are impossible for a computer.

As a side note, suppose your situation was better, and you try to cope with some decidable problem which has an exponential lower bound (i.e. all algorithms for this problem would require exponential time, not just brute force search, even the "smart" ones). Again, better hardware won't help you. For some intuition regarding your parameters, you have $\approx 10^{80}$ atoms in the universe, so performing this amount of operations is hopeless. What you need is a smarter algorithm, but we started with a problem that unfortunately has an exponential lower bound.


Does every problem in NP have an exponential time algorithm?

Yes, every NP problem has an exponential-time algorithm. One definition of NP is the "succinct certificates" definition: a language $L$ is in NP if, and only if, there is a relation $R$ on strings such that:

there is a polynomial $p$ such that, whenever $(x,y)\in R$, $|y|\leq p(|y|)$,
$x\in L$ if, and only if, $(x,y)\in R$ for some $y$, and
there is a deterministic Turing machine that decides if $(x,y)\in R$ in polynomial time.

So, to decide if $x\in L$, all you need to do is try all possible $y$s of length at most $p(|x|)$ to see if $(x,y)\in R$ for some $y$.  There are exponentially many possible values of $y$ to try.

To see the intuition behind succinct certificates, consider 3-colourability. There, a certificate is a 3-colouring of the graph. To describe a 3-colouring needs just a constant number of bits to say what colour each vertex of the graph has, so the length of the certificate is bounded by a polynomial. Obviously, a graph is 3-colourable if, and only if, it has a 3-colouring. And if I claim to have a 3-colouring of a graph, you can check that in deterministic polynomial time: just make sure I didn't give the same colour to two adjacent vertices.

To get a succinct certificate for any NP-problem, use the definition that a problem is in NP if it's decided by a nondeterministic Turing machine in polynomial time. Use a description of an accepting run of that machine as the certificate.


Kosaraju with connections between SSCs (strongly connected components)

Your complexity calculation is incorrect. If for each vertex you go over all of its out edges, in a directed graph you'd only get a $O(|V|+|E|)$ complexity and not $O(|V|*|E|)$. A complexity of $O(|V|*|E|)$ would be the case if for each vertex you performed an operation on all of the edges in the graph, which you have no reason to do.

$O(|V|+|E|)$ complexity is actually the same complexity as calculating the SCCs in the first place, and therefore your general idea can, in-fact, be used (be careful with the details).


Decreasing the weight of one edge of minimum spanning tree, prove the MST is unchanged

There is no necessarily a unique MST for a given G. So reducing an edge might trigger an MST finding algorithm to find a alternative MST. The question is if given MST remains an MST after the change.

Let's make some definitions:

$e$ is the edge we reduce its weight
$w(e)$ is the weight of the edge e
$w(T)$ is the weight of tree T (sum of all edges)

I will prove it by contradiction
Let's suppose that after decreasing the weight of of edge $e$ from $w(e)$ to $w'(e)$ T is no more a minimal spanning tree, and $T'$ is a minimal spanning tree.

First we consider the case where $e \in T'$

After the decrease of w(e)-> w'(e) the new graph is $G'$.
In $G'$ we have:

$w(T') < w(T)$ by assumption

$w'(e) + w(T' - {e}) < w'(e) + w(T-{e})$

$w(T'-{e}) < w(T-{e})$ and that is true both in G and G', since $\{T'-e\}$ and $\{T-{e}\}$ are same in both graphs

Then subsequently in $G$ we have
$w(T'-{e}) < w(T-{e})$

$w(e) + w(T'-{e}) < w(e)+ w(T-{e})$

$w(T') < w(T)$ which means that in G T is not a minimal spanning tree which is not true.

Now we consider the case where $e \notin T'$

Then in G' $w(T')< w(T)$ and by the same sequence

$w(T'-{e}) <  w(T-e)$ in both $G$ and $G'$

In $G$ we have consequently
$w(T'-{e}) + w(e) < w(T-{e}) + w(e)$ and if $T'' \equiv \{T'+e\}$ then

$w(T'') < w(T)$ which again contradicts the truth that T is MST in G.


Best case "skew height" of an arbitrary tree

For a binary tree, let $H(T)=\min_AH_A(T)$, where $A$ ranges over all favored-child assignments of $T$. Call $H(T)$ the skew height of $T$.
Here is a simple observation. The skew height of a perfect binary tree of (ordinary) height $n$ is $n$, too.

For a binary tree $T$, an edge is called a passing edge if one of the endpoints has exactly one child. We call a binary tree $M$ a b-minor of $T$ if $M$ can be obtained by removing a subtree or contracting a passing edge repeatedly.
For a binary tree $T$, what is its skew height? Here is a visual characterization.
The skew height of $T$ is the maximum (ordinary) height of all perfect binary trees that are also b-minors of $T$. Intuitively speaking, a binary tree is of skew height $s$ $\iff$ it "contains" a perfect binary tree of ordinary height $s$.
Proof. Since both removing a subtree and contracting a passing edge do not increase the skew height, $$H(T)\ge \max_{M\text{ is a b-minor of T}}\mathsf{height}(M),$$ where $\mathsf{height}(\cdot)$ is the (ordinary) height of a tree. On the other hand, by induction on the number of nodes of $T$, we can show that a binary tree of skew height $s$ must contain a b-minor that is a perfect binary tree of ordinary height $s$. $\quad\checkmark$.

Recall that $n$ is the number of nodes in $T$. We have,
$$H(T) \le \lceil \log_2(n+1)\rceil - 1.$$
Proof. Induction on $n$. The base case, $n = 1$ is easy to verify.
Suppose it is true if the number of nodes in $T$ is smaller than $n$. Consider a binary tree $T$ of $n$ nodes with root node $r$.

If $r$ has only one child, say, $a$, then $$H(T)=H(\text{the subtree rooted at } a)\le \lceil \log_2((n-1)+1)\rceil - 1\le \lceil \log_2(n+1)\rceil - 1.$$
If $r$ has two children, say, $a$ and $b$. Since the number of nodes in the subtree rooted at $a$ and the subtree rooted at $b$ is $n-1$, one of the subtrees has at most $\lfloor (n-1)/2\rfloor$ nodes. WLOG, suppose it is the subtree rooted at $b$. Then
$$H(T)=\max(H(\text{the subtree rooted at }a ) + 1, H(\text{the subtree rooted at } b)) \\
\le \max(\lceil \log_2(\lfloor(n-1)/2\rfloor+1)\rceil,\lceil \log_2((n-2)+1)\rceil -1) $$
Since $$ \lceil \log_2(\lfloor(n-1)/2\rfloor+1)\rceil=\lceil \log_2(\lfloor(n+1)/2\rfloor)\rceil=\lceil \log_2(n+1)\rceil-1,$$
we have $H(T)\le \lceil \log_2(n+1)\rceil-1.$ $\quad\checkmark$

Recall that $f(n)=\max_{T\text{ is a binary tree and }|T|=n}H(T)$. The above section has proved $f(n)\le \lceil\log_2(n+1)\rceil-1$.
On the other hand, the skew weight of the perfect binary tree with $2^m-1$ node is $m-1$. Hence,
$$f(n)=\lceil\log_2(n+1)\rceil-1.$$


Logarithm types are definitely a thing and have been noticed before by a number of people. In functional programming, a Type -> Type functor has a logarithm if it's representable, and then the logarithm is the representing object. See also this, this, and this. You are correct about the exponential functor being the bag functor, see e.g. this, where it's described as the fixed point of the derivative operation on endofunctors.


Search Algorithm with two areas of solutions

With no other given assumptions, it is a linear solution in the most optimal scenario.
One can have better solution (binary search) in problems where all the values after first true are true. But if there is only one element, it is a O(n) solution.


Is it possible to make data structure that will find MEX and support modification queries

Method 1
You can also use a bit trie — this is a trie made of bits of your numbers, thus it is represented as a binary tree (since there are only two types of bits — 0 and 1), and its depth is $\mathcal{O}{(log(n))}$.
When you add a number, you mark the vertex that representing this particular number as a full binary tree, and then you recursively go over its parents marking them as full binary trees if their left and right children are both full binary trees as well.
When you remove a number, you unset the "full binary tree" mark and do so for all its parents.
When you want to get MEX, you should do the DFS towards $x$, avoiding visiting subtrees which are marked as full (because there are no free values in such subtrees) and attempt to visit a left subtree first if you are allowed to by the x restriction.
class MEX {
  struct MEXNode {
    MEXNode *children[2];
    bool is_full = false;
    int cnt = 0;

  public:
    MEXNode() {
      children[0] = nullptr;
      children[1] = nullptr;
    }
  };
private:

  inline MEXNode *nonnull(MEXNode *& n) {
    if (!n) n = new MEXNode();
    return n;
  }

  void insert(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt++;
      n->is_full = true;
      return;
    }

    int cur_bit = (val & (1 << level)) >> level;
    insert(val, level - 1, nonnull(n->children[cur_bit]));

    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }

  // Remove an integer from the set
  void remove(int val, int level, MEXNode *n) {
    if (level == -1) {
      n->cnt--;
      n->is_full = n->cnt > 0;
      return;
    }

    int cur_bit = (val & (1 << level)) >> level;
    remove(val, level - 1, nonnull(n->children[cur_bit]));

    n->is_full = nonnull(n->children[0])->is_full && nonnull(n->children[1])->is_full;
    n->cnt = nonnull(n->children[0])->cnt + nonnull(n->children[1])->cnt;
  }

  // Find the minimum element >=x that isn't present in the set
  int get(int val, int level, MEXNode *n) {
    if (n->is_full) {
      return -1;
    } else if (n->cnt == 0) {
      return val;
    }

    int cur_bit = (val & (1 << level)) >> level;
    int ans = get(val, level - 1, nonnull(n->children[cur_bit]));
    if (cur_bit == 0 && ans == -1) {
      ans = get((val >> level << level) | (1 << level), level - 1, nonnull(n->children[1]));
    }

    return ans;
  }

  MEXNode root_node;
public:

  void insert(int x) {
    insert(x, 31, &root_node);
  }
  void remove(int x) {
    remove(x, 31, &root_node);
  }
  int get(int x) {
    return get(x, 31, &root_node);
  }
};

Method 2
Create a set of intervals $S$. If the interval $[l, r]$ is present in $S$, that means that the elements $l, l + 1, l + 2, \dots , r$ are in $S$.
Adding an element $x$ is handled like this:
If $[whatever, x - 1]$ is present in the set, remove it and add $[whatever, x]$. Likewise, if $[x + 1, whatever]$ is in the set, remove it and add $[x, whatever]$.
Removals are handled in this way:
Find the interval containing x. Split it into two intervals $[start, x - 1]$, and $[x + 1, end]$.
MEX queries are handled similarly:
Find the interval containing $x$ and output $end + 1$. This can be implemented using 2 std::set<std::pair<int, int>> in C++.
The first set indexes pairs by the first element (i.e. left end), and the second one by their second element (i.e. right end)
class MEX {
  typedef std::pair<int, int> interval;
  std::set<interval> s[2];
  std::multiset<int> values;
  void insert_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].insert({x, y});
    s[1].insert({y, x});
  }
  void remove_pair(interval p) {
    auto[x, y] = p;
    if (x > y) std::swap(x, y);
    s[0].erase({x, y});
    s[1].erase({y, x});
  }

  std::optional<interval> is_end(int x, bool left) {
    int idx = left;
    auto it = s[idx].lower_bound({x, 0});
    if (it != s[idx].end() && it->first == x)
      return *it;
    else
      return std::nullopt;
  }

 public:
  void insert(int x) {
    bool ok = values.find(x) == values.end();
    values.insert(x);
    if (!ok) return;
    auto p1 = is_end(x - 1, true);
    auto p2 = is_end(x + 1, false);
    if (p1 && p2) {
      interval i = {p1->second, p2->second};
      remove_pair(*p1);
      remove_pair(*p2);
      insert_pair(i);
    } else if (p1 && !p2) {
      interval i = {p1->second, x};
      remove_pair(*p1);
      insert_pair(i);
    } else if (!p1 && p2) {
      interval i = {x, p2->second};
      remove_pair(*p2);
      insert_pair(i);
    } else if (!p1 && !p2) {
      interval i = {x, x};
      insert_pair(i);
    }
  }
  void remove(int x) {
    values.erase(values.find(x));
    if (values.find(x) != values.end()) return;
    auto it = s[1].lower_bound({x, 0});
    if (it->first != x && it->second != x) {
      interval p1 = {it->second, x - 1};
      interval p2 = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p1);
      insert_pair(p2);
    } else if (it->first != x && it->second == x) {
      interval p = {x + 1, it->first};
      remove_pair(*it);
      insert_pair(p);
    } else if (it->first == x && it->second == x) {
      remove_pair(*it);
    } else if (it->first == x && it->second != x) {
      interval p = {it->second, x - 1};
      remove_pair(*it);
      insert_pair(p);
    }
  }
  int get(int x) {
    if (values.find(x) == values.end()) return x;
    auto it = s[1].lower_bound({x, 0});
    return it->first + 1;
  }
};

Usage

MEX mex;
mex.insert(int);
mex.remove(int);
mex.get(int); // Find the minimum element >=x that isn't present in the set

Reference
Sample Problem
Solution using Method-1
Solution using Method-2


Minimizing sum of $w_i(y_i - y_c)$ over $y_c$

$x_i$ is irrelevant, it doesn't appear in the objective function.
$y_i$ and $w_i$ are constant.
So the minimization simplifies to:
$$\operatorname*{argmin}_{y_c} \sum{i=1}^n w_i(y_i - y_c) = \operatorname*{argmin}_{y_c} \sum_{i=1}^n w_iy_i - \sum_{i=1}^n w_iy_c,$$
which is either
$$\operatorname*{argmin}_{y_c} -\left(\sum_{i=1}^n w_i\right) y_c $$
or
$$\operatorname*{argmax}_{y_c} \left(\sum_{i=1}^n w_i\right) y_c $$
So depending on whether the sum of your weights is positive or negative, either the highest or lowest $c_i$ should be $c$.


Difference in scale between mean page loading times and exponentially distributed page loading times?

The time to load a web application is a sum of multiple factors, including at least:

The round-trip latency to initiate a TCP connection to the server (or maybe multiple connections, depending on your application and your browser) -- also called RTT time.
The time to download all of the page and content that it causes to be downloaded.

The second factor depends on the amount of delay you're adding; the first doesn't.  Also, the multi-page application might cause more TCP connections, causing more of the first type of delay; but it downloads less data, so less of the second delay.

So there's no reason to expect things to scale as simply as you are expecting.  Instead, the resulting performance will be a more complicated function of page size, RTT time, and delay.

Heuristically, we can expect a RTT time of a few hundred milliseconds per TCP connection, though that will depend on how far the client is from the server.  You say there's an average delay of 1 second per 200 bytes downloaded, so for the single-page application, you expect 267KB / 200bytes = 1367 seconds of delay added, on average, due to your artificial delays; for the multi-page application, you expect 58KB / 200bytes = 297 seconds of delay added, on average.  Without the artificial delays, the time to download that much data might depend on the speed of your network.


MCTS how to prevent Selecting a TERMINAL state in TRAVERSAL Phase?

What you can do is to add a counter $t$ to each node, initially 0, indicating how many of its children are terminal.
When $t = c$ where $c$ is the number of children of a node, the node itself becomes terminal and increments the $t$ counter of its parent. Note that with this definition leaf nodes are automatically terminal, as they have no children, giving $0 = 0$.
As one more optimization, if a node has a terminal child that is losing, you can immediately mark its parent as terminal and winning.
Then, during selection you can ignore any terminal child.


Algorithm to determine if recursion was breadth first or depth first

Recall that both BFS and DFS are worklist algorithms.  This means they maintain a "worklist" of vertices that need to be visited, but haven't been yet.  You can think of the worklist as a list or set  of "stuff that needs to be done", where here the kind of tasks that need to be done are of the form "visit vertex $v$".  When DFS or BFS visits a vertex $v$, we find all its neighbors, and add each one that has not yet been visited to the worklist (if it is not already present in the worklist).

The only difference between DFS and BFS is in how they implement the worklist.  DFS implements the worklist as a stack.  BFS implements the worklist as a queue.

So, here is how you can test whether your sequence was obtained by DFS, by BFS, or by something else.  Replay the sequence of visited nodes.  Keep a worklist, just like DFS/BFS would, but use a set data structure, and add a timestamp to each item in the worklist recording when it first entered the worklist.  At each step, when you visit a node $v$, check that $v$ is in the worklist, and check its timestamp.  If its timestamp is the earliest of all items in the worklist, this is consistent with removal from a queue (i.e., BFS); if it is the latest of all items in the worklist, it is consistent with a stack (i.e., DFS); otherwise, it is neither.  Then, add to the worklist each neighbor of $v$ that has not yet been visited and that isn't already in the worklist, using the same timestamp for all of them (since they all entered the worklist on the same step of the sequence).

Iterate through the entire sequence like this.  If every step is consistent with DFS (i.e., consistently stack-like), then this sequence could have been generated by some DFS traversal.  If every step is consistent with BFS (i.e., consistently queue-like), then this sequence could have been generated by some BFS traversal.  If neither of these are true, then you know that this was generated by neither DFS nor BFS.

You can make this algorithm very efficient: at most a logarithmic slowdown compared to a DFS/BFS itself (and maybe even faster is possible).


My understanding is that a write-miss occurs when we want to write data to a location in main memory whose data is not currently in its corresponding cache block.
This is similar to a read miss: if the cache block that a memory location is mapped to does not contain the data of that memory location (indicated by differing tags), then some other memory location also mapped to that same cache block is currently present, and a miss occurs.
Similarly, we "miss" on a write if the memory location we want to write to isn't currently "in" its corresponding cache block, but rather, some other memory location's data currently occupies it.
The important question that follows a write-miss is "do we update the cache block corresponding to the memory location we just updated with that new data, or leave the old?" Perhaps the memory-location's data already occupying that cache block is more useful or being used more frequently than what we just wrote.


An $O(n)$ algorithm to FFT-evaluate an FFT evaluation

Let's answer your questions one by one.

You don't compute $W^2$ by squaring $W$ algorithmically. Rather, you compute $W^2$ "on paper", and you find out a formula for $W^2$. Given this formula, you can check that
$$ (W^2 X)_j = \sum_{k=0}^{n-1} (W^2)_{jk} X_k = nX_{-j}, $$
where $-j$ is the unique $k$ such that $j+k$ is a multiple of $n$. For example, if $n = 5$ then the correspondence between $j$ and $k$ is
$$
\begin{array}{c|c}
j & k \\\hline 0 & 0 \\ 1 & 4 \\ 2 & 3 \\ 3 & 2 \\ 4 & 1
\end{array}
$$
Let $Y = W^2X$. Then $Y_j = nX_{-j}$, and so we can compute $Y$ from $X$ in linear time $O(n)$.
Since $FFT(X) = W\times X$, $FFT(FFT(X)) = W\times FFT(X) = W \times (W \times X) = (W \times W) \times X = W^2 \times X$.
This is a calculation:
$$
\begin{align*}
W^2_{jk} &= \sum_{i=0}^{n-1} W_{ji} W_{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{ji} \omega_n^{ik} \\ &= \sum_{i=0}^{n-1} \omega_n^{i(j+k)} \\ &= \sum_{i=0}^{n-1} (\omega_n^{j+k})^i.
\end{align*}
$$
If $j+k$ is a multiple of $n$ then $\omega_n^{j+k} = 1$ and so
$$ W^2_{jk} = \sum_{i=0}^{n-1} 1^{j+k} = \sum_{i=0}^{n-1} 1 = n. $$
Otherwise, $\omega_n^{j+k} \neq 1$ and so we can use the formula for the sum of a geometric series to conclude
$$ W^2_{jk} = \sum_{i=0}^{n-1} (\omega_n^{j+k})^i = \frac{(\omega_n^{j+k})^n - 1}{\omega_n^{j+k} - 1} = 0 $$
since $\omega_n^{(j+k)n} = (\omega_n^n)^{j+k} = 1^{j+k} = 1$.


Don Knuth and MMIXAL vs. Chuck Moore and Forth -- Algorithms and Ideal Machines -- was there any cross-pollination / influence in their ideas / work?

There is some evidence: This paper was presented at the ACM SIGPLAN History of Programming Languages Conference (HOPL II, April, 1993), co-authored by myself, Chuck, and Don Colburn, an erstwhile colleague now unfortunately deceased. It references, in turn, a very early work that Chuck wrote when Forth was in what might be called an "alpha" form, "Programming a Problem-oriented Language".

I worked with Chuck from 1970 until 1982, when he left FORTH, Inc. to pursue chip-level implementations of Forth. I know that he referenced Knuth's books and papers for specific algorithms from time to time, but do not believe Knuth influenced the design of Forth in any way. In the time I worked with him, the two men never met. Whether Knuth was aware of Forth or of Chuck I cannot say.


What is the time complexity of the following program?

The running time of the function on an input $n$ can be expressed as: $$T(n) = T(\sqrt n) + \mathcal{O}(1)$$

which implies the running time of the function and the number of recursions differ only by a constant.

The recursive chain ends when $n$ has been reduced to some value $k$, where $k \le 2$. The number of recursions, $r$, can be expressed as: $$k^{2^r} = n \implies r = \log_2 \log_k n$$

It follows that the running time is then:

$$\Theta(\log_2 \log_k n) = \Theta(\log \log n)$$


Complexity for find pairs with sum - BST

It would be $O(n^2)$ in the worst case. Suppose root of BST is $15$, all left nodes are $7$, and all right nodes are $21$. We want to find all pairs which their sum is $28$. Hence, you should report all $\frac{n}{2}\times \frac{n}{2}$ items (all left nodes with all right nodes). Hence, your algorithms should report $O(n^2)$ pairs in the worst case.


Lower Bounds for Size of Independent Set in a Graph?

The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.


DFA that accepts any integer $n$ such that $n \bmod 7 =1$

I assume you are talking about integers encoded in some base $b \geq 2$, and we're reading the integer from left to right.

An inductive hint: say we have read the number $n$ so far, and our inductive assumption is that we are in state $n \bmod 7$ (so we have 7 states). We read the digit $d$. Our next state should be $bn + d \bmod 7$. How do we correctly determine what state to go to, since we don't know $n$?

Well the trick is that while you don't know $n$, you do know $n \bmod 7$. And:

$$bn + d \equiv b(n \bmod 7) + d\mod 7$$

So for example, in base $10$, if we are in the state $3$ (meaning $n \equiv 3 \mod 7$) and we just read the digit $8$, our next state will be  $10\cdot 3 + 8 \equiv 3 \mod 7$. In other words, state $3$ points to itself on reading digit $8$ in base $10$.


There is first-order reductions.

See Immerman's book, Chapter 3, Theorem 3.26 which states that $\mathrm{REACH}_a$ is complete for $\mathrm{P}$ via first-order reductions.

Also, see my question, for related information on $\mathrm{NP}$.


Subset Sum: reduce special to general case

You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem.

For the other way round (i.e. a reduction from general to special):

Suppose you are given a set $S = \{x_1, \dots, x_n\}$ and a number $K$ and you have to determine if there is some subset of $S$ which sums to $K$.

Now you want to solve this problem, given an algorithm for the case where you can determine if some subset sums to $0$.

Now if $x_i \gt 0$, we have an easy reduction: $S' = \{x_1, x_2, \dots, x_n, -K\}$.

$S'$ has a subset of sum $0$ iff $S$ has a subset of sum $K$.

The problem occurs when we can have $x_i \le 0$ for some of the $i$.

We can assume that $K \gt 0$ (why?).

Suppose the sum of the positive $x_i$ is $P$ and the negative $x_i$ is $N$.

Now construct a new set $S' = \{y_1, y_2 \dots, y_n\}$ such that

$y_i = x_i + M$ where $M = P + |N| + K$.

Each $y_i \gt 0$.

Now run the zero-subset-sum algorithm on the sets

$ S' \cup \{-(K+M)\}$

$ S' \cup \{-(K+2M)\}$

$ S' \cup \{-(K+3M)\}$

$\dots$

$ S' \cup \{-(K+nM)\}$

It is easy to show that if $S$ has a subset of sum $K$, then at least one of the above sets has subset of sum zero.

I will leave the proof of the other direction to you.


Intuitively, the language is exactly the set of words that have $a$ in all the odd places. Thus, the corresponding NBW (in fact, $DBW$) has three states, $q,s,r$, where $q$ is initial, $s$ is accepting, and $r$ is a rejecting sink. The transitions are $\delta(q,a)=s, \delta(q,b)=r$, and $\delta(s,a)=\delta(s,b)=q$.


Is it decidable whether a Turing machine will ever leave the start state on any input?

I would say decidable. Here is the idea.

Firstly, let your alphabet be $\Sigma$, including the empty symbol. I claim that unless you have in the transition function $(s_0, x) \to (s_i, \dots)$ for every $x \in \Sigma$ and $ i \neq 0$ your machine is not the desired one. Why this is true?
Suppose there is such $x$ for which TM doesn't change the initial state. Fill the tape with all these $x$'s. Done.

Here I had the assumption that we can have any initial tape as we want. If you consider only finite non empty input the problem becomes much harder.


There is no single answer: you could build a text editor in any way you want.
One simple architecture for a text editor is to have a single process, which blocks on I/O when it is waiting for the user to provide input.  But it's also possible for a text editor to be built in a multi-threaded way with multiple processes, e.g., spawning one thread to do spellchecking in the background or anything else.


How to find total number of minimum spanning trees in a graph with n edges?

I'm hoping you misremembered the question, as the number of MSTs (minimum spanning trees) is not uniquely determined by the number of edges.  It depends on what edges are and are not present and also what their weight's are.

For example, if the graph has 21 vertices and 20 edges, then it is a tree and it has exactly one MST. On the other hand, if it has seven vertices and 20 edges, then it is a clique with one edge deleted and, depending on the edge weights, it might have just one MST or it might have literally thousands of them.

(A clique on seven vertices has 21 edges, which is only one more than your graph is allowed. If all the edge weights were the same, every subtree would be an MST and, by Cayley's formula, there are $7^5=16807$ different trees with seven vertices.)


One possible hypothesis:

Javascript is interpreted, which can slow things down.

When you compare two strings, this will invoke a string comparison routine that is coded directly in assembly language or C, and thus string comparison will probably be about as fast as the architecture can possibly compare strings.  In contrast, when you hash strings, you have to execute multiple instructions in Javascript, which might incur overhead from an interpreter.

Another possible hypothesis:

Numbers in Javascript are a floating-point type.  There is no integer type in Javascript.  Your rolling hash probably involves what looks like integer arithmetic.  However, under the covers this is probably getting interpreted as operations on double-precision floats, which can be a bit slower.  This might also make your hash-based schemes slower.  Some Javascript engines might optimize this to integer arithmetic in certain circumstances, but no guarantees about whether any particular Javascript engine will or won't be able to do that in any particular case.


Do problems in P have a minimum number of YES and NO instances?

If a problem has only "YES" instances (resp. only "NO" instances), then the associated language, which is our formalization of a "problem" contains every word in $\Sigma^*$ (resp. no words), with $\Sigma$ being the underlying alphabet.

Both $\Sigma^*$ and $\emptyset$ are regular languages, and in particular, are both in $P$.

So yes - there are trivial languages are in $P$.

In fact, this argument also works when there are finitely many YES or NO instances, since finite languages are regular, and also their complements are.

So for a language not to be in $P$ it must first of all have both infinitely many YES and infinitely many NO instances.


Are there variations of the regular runtimes of the Big-O-Notation?

I was wondering, if there are variations of those in reality such as $O(2n^2)$ or $O(\log (n^2))$, or if those are mathematically incorrect.

Yes, $O(2n^2)$ or $O(\log (n^2))$ are valid variations.

However, you will see them rarely if you would see them at all, especially in the end results. The reason is that $O(2n^2)$ is $O(n^2)$. Similarly, $O(\log (n^2))$ is $O(\log n)$. That might be surprising to beginners. However, those equalities are more or less the very reason why big $O$-notations were introduced, to hide a multiplicative constant factor that is often hard to pin down and relatively insignificant.

  Would it be a right thing to say that it is possible to improve a $O(5n^2)$ to a $O(3n^2)$?

It is not an improvement at all if the time-complexity of an algorithm is changed from $O(5n^2)$ to a $O(3n^2)$ or from $\Omega(5n^2)$ to $\Omega(3n^2)$, because $O(5n^2)$ is $O(3n^2)$ while $\Omega(5n^2)$ is $\Omega(3n^2)$. So it is incorrect to say the time-complexity is improved from $O(5n^2)$ to $O(3n^2)$. It is correct to say the time-complexity of an algorithm is improved from $5n^2$ to $3n^2$, of course.

Exercise 1. Show that $O(5n^2)=O(3n^2)=O(n^2)$.

Exercise 2. Show that $O(\log n)=O(\log (n^2))$.

Exercise 3. Show that $\Omega(n^2+n)=\Omega(n^2)$.


The relationship between degree and the number of leaves of a tree?

As you said the degree of a tree, probably $T$ is a rooted tree. Hence, the relation between the number of leaves $n$ is $\text{deg}(T) \leq n$, as each child of the root is terminated to at least one leaf


There are many issues in your question. I am no longer very expert in some
of them, but let's try.

Basically, a standard program as you like it takes some input $I$,
satisfying some property $P$, and does things with it so as to obtain
an output $O$ satisfying some property $Q$ involving $I$ and $O$:
$Q(I,O)$.

This program solves a problem corresponding to a constructive proof
that $\forall I, P(I) \implies \exists O, Q(I,O)$. The problem is to
find $O$ when given $I$. This may actually be read as a specification of the problem, of the program.

It is easy to apply this to a sorting program, for example.

This works nicely in functional programming.

But when you quit functional programming, things become harder to
explain.

Typically, printing a string is a side effect, hence not functional.

If instead of printing you were considering just producing the string
"Hello world", for whatever purpose, the you would have a functional
program meeting a degenerate case of the above schema, because there
is no input.

The problem reduces to: produce the string "Hello world"
and corresponds to the specification $\exists O, O=\text{"Hello world"}$.
The lack of input makes the universal quantifier unneeded.

But printing is something else, as is network reconfiguration. They are not directly functional operations.

Now, it is possible to simulate non-functional structures in a
functional context by building appropriate domains of computation. But
this often makes things a lot more complex. And the understanding I
tried to give is no longer so obvious.

Dealing with these issues has been one of the main purposes of
denotational semantics. Much of the research in language design is
about bridging the gap between functional understanding and the
requirements of non functional practices.


Are you aiming to simply allow recursive functions or specify only recursive functions. The following grammar allows recursive functions:
function      := id '(' parameter ')' '=' function_body ;
function_body := conditional
               | expression
               ;
expression    := function_call
               | <other expression types>
               ;
function_call := id '(' parameter ')' ;

Specifying only recursive functions would require a context-aware grammar (BNF is context-free). You can approach the problem outside of the grammar specification though and check for recursive functions later in your parser / compiler pipeline.
Checking for recursion outside of the grammar allows you to more easily identify cyclic recursion (not just f calling f but something like f -> a -> b -> c -> f).


I believe it means that $\sigma,\sigma$ should share the same prefix up to position $i$.
Then the quantification ranges over all possible extensions of this prefix from state $\sigma(i) = \sigma(i)'$.


Insertion sort Pseudo code vs implementation?

The following two points might clear your confusion.

The pseudocode in the book is following $1$ based indexing. Your code is following $0$ based indexing.

Your code is technically doing nothing in the first iteration of the while loop. In the first iteration $i = 0$, therefore $j = -1$. Since $j<0$, the inside while loop is not executed. And it keeps $A[0] = key$ to its original value. Effectively, your code starts executing from $i = 1$, which is equivalent to $j = 2$ in CLRS implementation.


Protocols for "almost equality" with one-sided error

Here are two solutions. In both cases, the inputs are $x,y \in \{0,1\}^n$, and we are interested in checking whether the Hamming distance between $x$ and $y$ is at most $k$ or not.

Solution 1 (D.W.):

The two parties decide on a random string $z \in \mathbb{Z}_{2k+3}^n$, compute $\alpha = \langle x,z \rangle$ and $\beta = \langle y,z \rangle$, and accept if $\alpha - \beta \notin \{k+1,k+2\}$.

If the Hamming distance between $x$ and $y$ is $d$, then $\alpha - \beta$ is distributed as the sum of $d$ many $\pm 1$ random values. When $d \leq k$, clearly $\alpha - \beta \notin \{k+1,k+2\}$. Conversely, when $d > k$, the probability that $\alpha - \beta \in \{k+1,k+2\}$ is $\Omega(2^{-k})$.

Solution 2 (Sa'ar Zehavi):

The two parties decide on a random partition of $\{1,\ldots,n\}$ into $k+1$ parts, and run the one-bit equality protocol on each of them. They accept if the equality protocol succeeds (declares "equal") on at least one of them.

If the Hamming distance between $x$ and $y$ is at most $k$, then clearly the parties always accept. Otherwise, with probability $\Omega(e^{-k})$ all the $k+1$ parts will be different, and so the equality protocol will fail on all of them with probability $\Omega(2^{-k})$.


How would one use "BUT" logic in a ternary logic computer in a practical way?

In the article "The A-Z of Programming Languages: INTERCAL" Naomi Hamilton (Techworld Australia) interviews Don Woods, one of the authors of INTERCAL. More about INTERCAL.

On page 3 of the article the last question is:

  Naomi: "Is there anything else you'd like to add?"

  Don: "... Much of the fun of INTERCAL comes from figuring out how it can be used to do something that would be trivial in other languages. More fun is had by extending the language with weird new features and then figuring out what can be done by creative use of those features."

Apparently the authors of TriINTERCAL took the spirit of the language to heart, yet avoided adding an entirely useless operation.

TriINTERCAL differs from INTERCAL only in the width of the data types (one-spot data types are 10 trits wide and two-spot data types are 20 trits wide), and in the operators available in expressions. "AND" and "OR" are generalizations of the INTERCAL binary versions, "BUT" is new, and "Sharkfin" and "What" are two different interpretations of "XOR" (both of which are available in TriINTERCAL). "Mingle" mingles trits, rather than bits, whereas "Select" ANDs the two original numbers, then sorts all the bits in the first number corresponding to 2's in the second number to the least significant end, 0's in the second number to the most significant end, and 1's in between them.

"AND", "OR", "Mingle", and "Select" operate just like their binary counterparts if no trits with the value 2 are present.

Here are TriINTERCAL's operators (According to Esolang.org):

$$
\begin{array}{cc|cc} \text{AND}\quad\qquad & \& & 0 & 1 & 2 \\
\hline
& 0 & 0 & 0 & 0 \\
& 1 & 0 & 1 & 2 \\
& 2 & 0 & 2 & 2 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{OR}\quad\qquad\;\;\; & \lor & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 1 & 1 & 2 \\
& 2 & 2 & 2 & 2 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{BUT} \quad\qquad & @ & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 0 \\
& 1 & 1 & 1 & 1 \\
& 2 & 0 & 1 & 2 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{SHARKFIN} & \land & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 1 & 2 & 0 \\
& 2 & 2 & 0 & 1 \\
\end{array}
$$

$$
\begin{array}{cc|cc} \text{WHAT} \, \qquad & ? & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 2 & 0 & 1 \\
& 2 & 1 & 2 & 0 \\
\end{array}
$$

  Question: "How would one use “BUT” logic in a ternary logic computer in a practical way?"

Taking some liberty with the English language and the meaning of the TRiINTERCAL operators I'll explain it thusly:

The "AND" operator: Max(True), unless one is false.

The "OR" operator: Max(True), unless both are false.

The "BUT" operator: Find the 'middle ground' if allowed; if both sides fully agree then sway that way. Put another way: Always "1" unless one input is "0" or "2", then choose that instead; with "0" overriding "2".

The "SHARKFIN" operator: Addition (Mod 3). Put another way: Add and wrap, never exceeding two.

The "WHAT" operator: If both sides agree it's false, prefer "1" over "2"; oops, disregard that ... [But you weren't asking about what] ;)

  Question: "How could such an operation be used in practice (either on single trits or multiple trytes)?"

The webpage "MuppetLabs" website describes it this way:

  "In TriINTERCAL programs the whirlpool (@) denotes the unary tritwise BUT operation. You can think of the whirlpool as drawing values preferentially towards the central value 1. Alternatively, you can think of it as drawing your soul and your sanity inexorably down....".

  "As for operators, ? is always subtract without borrow, and ^ is always add without carry. V is the OR operation and always returns the max of its inputs. & is the AND operation, which chooses 0 if possible but otherwise returns the max of the inputs. @ is BUT, which prefers 1, then 0, then the max of the remaining possibilities. Rather than add more special symbols forever, a numeric modifier may be placed directly before the @ to indicate the operation that prefers one of the digits not already represented. Thus in files ending in .5i, the permitted unary operators are ?, ^, &, @, 2@, 3@, and V. Use of such barbarisms as 0@ to represent & are not permitted, nor is the use of @ or ^ in files with either of the extensions .i or .2i. Why not? You just can't, that's why. Don't ask so many questions.".

[NOTE: In my opinion the Truth table provided by Esolangs (for "WHAT") is incorrect, it should be this:]

$$
\begin{array}{cc|cc} \text{WHAT} \, \qquad & ? & 0 & 1 & 2 \\
\hline
& 0 & 0 & 1 & 2 \\
& 1 & 1 & 0 & 1 \\
& 2 & 2 & 1 & 0 \\
\end{array}
$$

Please see Esoteric Programming Languages for less information.


I'm assuming you're only allowed to use the 1x40 slabs horizontally or vertically. They thus cover entire rows or columns. We can rephrase your problem as minimum vertex cover in a bipartite graph. The bipartite graph consists of 40 row vertices and 40 column vertices. Connect two vertices if the corresponding point in the grid is 1. The minimum number of slabs needed to cover all 1s is exactly the minimum vertex cover in this bipartite graph. In bipartite graphs, minimum vertex cover equals maximum matching, so the problem is algorithmically feasible. In order to find a concrete algorithm, just look for algorithms for solving minimum vertex cover on bipartite graphs.


Let $A$ denote the adjacency matrix, $A^k$ its $k$th power, and $(A^k)_{ij}$ the entry of $A^k$ at row $i$, column $j$.  Then $(A^k)_{ij}$ is a count of the number of paths of length $k$ from node $i$ to node $j$.

Let $M = \text{Id} + A + A^2 + A^3 + \cdots$.  Then $M_{st}$ is a count of the number of paths (of any length) from source $s$ to destination $t$.  So, we just need to compute the matrix $M$.  The matrix $M$ can be computed using the matrix identity

$$M = (\text{Id} - A)^{-1}.$$

Thus, with a matrix subtraction and inversion, then looking at the $u,j$ entry of the resulting inverse, you can obtain a count of the number of such paths.

This includes paths where a node can be repeated.  If you want to count the number of simple paths, then the problem is #P-complete for general graphs (and thus likely has no efficient algorithm), or can be done in linear time for directed acyclic graphs by topological sorting and then using dynamic programming.


Given n standard C++ STL maps, can I merge them?

STL maps are stored in a data structure which is effectively sorted by key, typically some kind of binary search tree. BSTs have the property that finding the smallest key and finding the next larger key are both amortised O(1) (assuming you can find a node's children in constant time).

So doing your merge is similar to merging n sorted arrays, which has complexity $N log n$, where $N$ is the total number of elements in all the arrays. (Sorting the concatenation of all the arrays is $O(N log N)$, which is both practically and theoretically slower.

A simple $O(N log n)$ algorithm is to repeatedly do the following until only one array is left:

Divide the arrays into two $n/2$ pairs. If there is an odd number of arrays, one array is treated as though it were paired with an empty array.
Merge each pair into a single array using the standard merge algorithm, which involves iterating through both arrays in parallel.

The total number of elements scanned in each iteration is at most $N$. (It will be slightly less because the merge procedure combines two elements with the same key, so that the next iteration will involve fewer elements. But $O(N)$ is an acceptable estimate.)

Since the number of trees is halved each time, it will take $\lceil log_2 n\rceil$ iterations to reduce the number of groups to one. So the he total time is the product of the number of iterationss and the total number of elements scanned, which is $O(N log n)$.


Restrictions to counter machines capturing LBA

Programs with natural numbers as data and as instructions increment, decrement and zero test are know as register machines or counter automata. (Wikipedia cites several sources, usually I refer to Minsky).

Their power is that of the Turing machine, that is, they accept recursively enumerable sets (strings or numbers).

Thus they are more general than the LBA, which is more a complexity class (as mentioned in the comments). The length of the space used for computations is linear, otherwise the LBA are Turing Machines.

To translate that restriction to counter automata I would suggest to restrict the variables to at most exponential in the size (length) of the input. First, you can code such variable by markers on the tape. That would prove one inclusion. I expect that every LBA can be simulated by an exponentially bounded counter automaton, after all, the tape is just a number an writing on the tape is changing a digit. There is a standard construction that translates the two sides of the tape (right and left from the reading position) as two numbers, and moving the head is just a multiplication/division, deciding the element under the reading head is modulo counting. You need extra counters (variables) for these operations and in particular you need the zero test.


Is it possible to use "and", "or" "not" as relation/predicate in an ontology? In order to represent causality?

The ontologies that are used today are mostly based on Description Logics (DLs). The basic building blocks of DLs consists of concepts and relationships between concepts where a concept represents a set of individuals (elements) and a relationship states that an individual of one set is related to an individual of another set.

A good book in this regards is An Introduction to Description Logics. There are different DLs with different expressivities and indeed many DLs exist that allow for negation and relations. A freely available tool for creating ontologies is Protege.

The <s,p,o> you refer to is related to RDF data and RDFS which do not support negation. Roughly RDFS (similar to relational DB schemas) can be seen as defining the schema and RDF as defining the data (similar to the data of a relational database).

How to design what you require depends on the inferences you want to make from your ontology. Since you don't want to reason over the ontology, you can really model this however you want. Though I am wondering whether using an ontology is the most appropriate if you do not intent do any reasoning.

Option 1: Using concepts

Class: D
  EquivalentTo: A or B
  SubClassOf: C

This will result in any individual belonging to A or B to be inferred to belong to C as well. Concept D is introduced to provide a name for the concept A or B.

Option 2: Using Relations

Class: D
  EquivalentTo: A or B

ObjectProperty causes:
  Domain: D
  Range: C

This will result in the inference that whenever two individuals a and b are related via causes (written as causes(a, b)), it will infer that a belongs to D and b belongs to C.

On my blog I have a few posts that give some explanations wrt ontologies as well as some examples.


Are there any known lower-bounds for complexity on Non-determinsitic machines

No.  There are no known polynomial bounds.  The best lower bounds known are merely linear.

As described here, the situation for circuits at least is "quite depressing": there are no known lower bounds that are better than $\sim 4n$.  That's the case even when you pick the problem.  There is no explicitly known problem where we can prove a lower bound better than $4n$.

Of course, for many problems it is easy to get a lower bound of $n$, by noting that for some functions it is necessary to read all of the input bits.  So we can do only a constant factor better than the trivial lower bound.

Moreover, it is easy to prove (by a counting argument) that there exist functions that require at least $2^n/\text{poly}(n)$ gates to compute.  The catch is that this proof is non-constructive: we don't know an explicit example of such a function.  So there is an exponential gap between the best lower bound we know how to prove, and what we know must be the actual best lower bounds (even though we don't know how to prove it for any specific problem).

I don't expect anything fundamental to change if you replace circuits with RAM machine algorithms.  Moreover, this shows that we don't know how to prove useful/non-trivial lower bounds for deterministic algorithms.  Proving useful/non-trivial lower bounds for non-deterministic algorithms is even harder.

(The situation might be slightly different with Turing machines, as they're a bit slower/less powerful than RAM machine algorithms -- but you asked about the latter, so I assume we can ignore this.)

You might enjoy perusing the lower-bounds tag on CSTheory.SE.


Are Context Sensitive Grammar with Polynomial Complexity Time?

To your first question, the answer is affirmative:

On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely exist tasks which take linear space and polynomial time.

On the other hand, that doesn't mean every task that takes linear space takes only polynomial time. However, until now, nobody has been able to prove either way. Even for the hardest problems that take polynomial space, the PSPACE-complete problems, it is not known whether they can be done in polynomial time: we don't know whether PSPACE = P. If you can prove for a single PSPACE-complete problem that it can be done in polynomial time, or that it cannot, you will be famous in computing science forever. In practice, for such problems, we have no better than exponential algorithms.

To answer your second question: parsing context-sensitive grammars is PSPACE-complete, so it takes exponential time in practice; it takes only polynomial time for growing context-sensitive grammars.


How to solve the following equation: $(k-1)2^h + k(2^{h-1}+1) \leq 2^{\lfloor\lg (n)\rfloor}$?

Before starting, let me note that there seems to be an "off by 1" issue with the way that height is measured. It seems that you should replace $h$ throughout with $h+1$.

First of all, let us notice that $2^{\lfloor \lg n \rfloor} \leq 2^{\lg n} \leq n$.
Therefore
$$
(k-1)2^h + k(2^{h-1} + 1) \leq n.
$$
Next, notice that
$$
(k-1)2^h + k(2^{h-1} + 1) = k(2^h + 2^{h-1} + 1) - 2^h.
$$
Therefore
$$
k(2^h + 2^{h-1} + 1) \leq n + 2^h.
$$
This immediately implies that
$$
k \leq \frac{n + 2^h}{2^h + 2^{h-1} + 1} \leq \frac{n + 2^h}{2^h + 2^{h-1}} = \frac{n + 2^h}{(3/2)2^h}.
$$

Now, $h + 1 = \lfloor \lg n \rfloor \le \lg n$, and so $2^{h+1} \leq n$, implying $2^h \leq n/2$. Therefore
$$
k \leq \frac{n+2^h}{(3/2)2^h} \leq \frac{n+n/2}{(3/2)2^h} = \frac{(3/2)n}{(3/2)2^h} = \frac{n}{2^h} \leq \left\lceil \frac{n}{2^h} \right\rceil.
$$


Can we do better than $O(n\log n)$ building a balanced binary tree?

If I understand your question correctly, then yes of course you can build a balanced binary tree in $O(n)$ time. Here is a simple pseudocode:

L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
  n = q.pop
  if k < L.size:
     n.left = node{value=L[k]}
     k++
     q.add(n.left)
  if k < L.size:
     n.right = node{value=L[k]}
     k++
     q.add(n.right)

It is not hard to see that this code does run in linear time and builds a balanced binary tree.

What you cannot do, is build a balanced binary search (ordered) tree in $O(n)$ time (using only comparisons on the values). The algorithm above does not guarantee that the value on the root is greater than or equal to every value in the left sub-tree and is less than or equal to every value in the right sub-tree, for every sub-tree.

The algorithm above does not guarantee it and neither does the conc-tree (using appends and prepends). From the wikipedia page, it only guarantees $O(1)$ amortized time for appends and prepends. For inserts, it can only guarantee $O(\log n)$ time.