For what data structures is jump search practically useful?

But what are contexts in which jump search actually makes sense as the most efficient method of searching data that was not specifically constructed to be ideal for jump searching?

Any context in which data is stored on a physical medium that allows forward jumping quicker than backwards jumping is a candidate. Just think of an ordinary hard drive. Its disk spins in a specific direction, making a forward jump much quicker than a backwards jump. To jump one unit backwards you need the disk to complete (nearly) a full rotation whereas jumping one unit forwards is near-instantaneous. Tape is another example, though here it is mostly the change of direction that is costly rather than backwards jumping specifically. For data stored in RAM, a CPU architecture might be specifically optimized for forward search rather than backward search (in principle, caching and branch prediction might cause differences in the speed of forward and backwards jumping).


Strategies for becoming unstuck in understanding TCS

Abstraction is pretty much bread and butter in computer science but unfortunately it is hard to teach explicitly.

In my opinion, understanding concepts is more important than being able to mechanically calculate or prove stuff. Sure, you need to know your way around some elementary methods, but the meat lies elsewhere.

First of all, you have to grasp the content to some extent. To this end, I have found it useful to ask the following question whenever something is unclear to you:

Why are we doing this?
What are we going to use this for?
What similar things does this relate to?
How do other sources explain it?
What exactly do I not understand?

After you have answered these questions (or discovered follow-up questions and treated them the same way) and still have problems, go to your teachers (or here). By now you should be able to formulate a focused, precisely formulated question; answering such questions is your teachers' job (and StackExchange's philosophy).

Other than that, it is exercise and experience. Try to reproduce proofs after having read them; take care to not learn them by heart but distill the important ideas from them. After some time, you should be able to reproduce all basic proofs by filling in gaps between the major steps. Even later, you will begin to see patterns in statements and proofs. This is how people look at a statement and say "Oh yeah, sure, use method X with theorem Y and then just use Z to get what you want.". It is pattern recognition fueled by years of training. Be patient.

As for basic exercises, go and find text books with some. Off the top of my head I can refer to Concrete Mathematics by Graham, Knuth, and Patashnik. This book is not only a precious toolbox for computer scientists, it also contains loads of exercises with solutions (!). Remember to attempt to solve them before looking up the answers and to reproduce answers you had to look up.

Another useful book is Introduction to Algorithms by Cormen, Leiserson, Rivest and Stein. Included is a sizeable chapter on mathematical basics. It also contains many exercises; solutions are available via the linked page (Supplemental Content). There is also a video lecture by one of the authors which may go nicely with the book.

For introductore lectures regarding proofs, have a look at Linear Algebra Proofs on Khan Academy. I have not watched them, but hopefully they are both basic and helpful. There are many more proofs on Khan Academy; I just figure that linear algebra proofs might fit computer science best. Do no hesitate to watch others, too.


The algorithm should say "choose $p \in S'$", that is, the text is the correct version, rather than the pseudocode.

Note how the algorithm works:

$S',S_{1},\ldots,S_{k}$ form a partition of $S$ (i.e. every element of $S$ is in exactly one of $S',S_{1},\ldots,S_{k}$).
At each step it chooses which $S_{i}$ to put $p$ into.
Initially $S' = S$, and $S_{i} = \emptyset$ for all $i$.

So $S'$ is the set of points that still need to be covered, and $S_{i}$ is the set of points covering by hyperplane $i$, in some abstract sense. Thus the algorithm, at each iteration, picks an uncovered element from $S'$, and puts it in some $S_{i}$.

Interestingly, this error made it all the way to the journal version.


Algebraic (spectral) algorithms for the minimum spanning tree problem

In short: no, not that I know of and I would be surprised if they exist.
For something longer, read on:

I don't think the spectrum of a graph can be of much use in finding an MST. The main reason is this: weights of a graph aren't part of the spectrum of a graph! An MST only makes sense on a weighted graph.

The only thing I see we could try, if all weights are integral, 'unfold' the graph such that all weights are unit-weights (so an edge of weight $32$ becomes $32$ edges and $31$ nodes in them) and mark the original nodes and make a min-cost tree that spans the original edges. After this transformation, the spectrum might contain all relevant info, but this transformation step makes our new graph simply horribly large, so any algorithm based on this will have an awful running time. This is simply a bad idea.

I've never heard of a useful way to 'attach' weights to edges in the adjacency matrix and connect them to the spectral properties, either. It doesn't seem likely to work, although proving a vague method won't work is of course impossible.

Of course, the fact that spectral properties likely aren't useful doesn't mean algebraic methods in general won't work. What is important is that you don't leave the edge weights behind. However, most other algebraic methods are used for exponential time algorithms and I'm not aware anyone has constructed something algebraic for MST.


Computer science fields that deal with peer-to-peer systems

Distributed systems, algorithms and even graph theory are fields that are likely to be relevant.

But, in a sense, "fields" aren't particularly relevant. You don't get a PhD "in a field" but, rather, by finding an advisor who wants to do a research project with you. That person would probably be in one of the fields I've suggested but being in a field isn't a formal status.


What is the most effective way to learn, understand, and utilize an algorithm?

To be an algorithm designer, you have to do some steps.

First, learn the basics of algorithmic thinking. You can learn it by using a simple programming language book. Choosing the language is not important. You can take a look at this page for finding a book. After finishing this step, you have to be able to present pseudocode (or code written in a specific language) for simple problems, for example:

Searching in a list: there is a list of numbers, and we want to see a specific number is in the list or not.
Sorting a list
Finding the greatest common divisor of two numbers

Second, learn the important data structures— link-list, stack, queue, and tree— and their algorithms. For doing this step, you can read the books of data structure written for bachelor students of computer science. For example, Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni is a good book. At the end of this step, you have to know/do the following things:

What is a data structure? How we can iterate over the elements of a data structure? How we can add a new item(/remove an item) from the data structure?
What are the main features of each data structure?

Third, learn conventional algorithm design techniques— divide and conquer, dynamic programming, greedy, back-track, branch and bound. For doing this step, you can read the algorithm design books written for bachelor students of computer science. For example:

Foundations Of Algorithms, Richard Neapolitan
Introduction to Algorithms, Thomas H. Cormen, et al. (Chapters 1-17)
After doing this step, you can solve a large range of algorithmic problems, like the problems that can be found on this website: onlinejudge.org.

Forth, learn specialized algorithm design techniques, like randomized algorithmic techniques, parallel algorithmic techniques, distributed algorithmic techniques, approximation algorithmic techniques, etc. For each case, there are some books written for graduate students of computer science.

Besides, there are some other steps, like learning the basics of the theory of computing, complexity classes (NP-complete and P-complete theories), and a lot of other things. It depends on your goal and the level that you want to be reached.


The axes are in logarithmic scale, and so don't really have a zero point. What you are seeing is
$$ \log P = \min(\log I + \log \beta, \log \pi). $$
The striking part is that the slope of the line is always the same.


You can implement, on a RAM machine, an interpreter that simulates the behavior of an arbitrary Turing machine (that's just a matter of programming, and there's nothing conceptually interesting or difficult about it); then use it on this particular Turing machine.  That's much easier to do, but might not lead to nice code for the RAM machine.
Or, you can understand/reverse-engineer the algorithm the Turing machine is using (this could be difficult), and then figure out how to implement that algorithm on a RAM machine (which is just a matter of programming once you understand the algorithm).
Asking "how do I write code on a RAM machine?" is not very different from "how do I write code in assembly language?"; you just do it, and there's not a lot of deep scientific or conceptual ideas needed, once you know what algorithms you are using.


How is the Time Complexity of a Function Problem different than its corresponding Decision Problem?

The Wikipedia article is confusing.

There are two things going on here.

Here's first thing: the complexity class P is defined to be a class of decision problems.  Thus, by definition, no function problem is in P.  So it's correct that the decision problem for gcd is in P, but the function problem for gcd is not.  Of course, this is pretty trivial.  So the first thing is not very interesting -- but it does explain why the Wikipedia article makes that odd comment about the decision problem for gcd being in P.

The second thing is more interesting: is there a difference in the running time between the decision problem and function problem?  Sometimes there is.  For instance, consider factoring.  A function problem is: given a number $t$, factor $t$ into a product of primes.  A decision problem is: given a number $t$ and primes $p_1,\dots,p_k$, check whether $t = p_1 \times \dots \times p_k$.  There is no known polynomial-time algorithm for the function problem, but there is an easy polynomial-time algorithm for the decision problem.  So, it's apparently easier to check whether the answer is correct than to find the answer.  Indeed, for any NP-complete problem, we believe it is easier to check the answer than to compute it, so the function problem appears to be harder than one plausible formulation of the decision problem.  (For that reason, when we turn function problems into decision problems, we usually do it in a different way than the one you mention.)

What about for gcd?  The function problem is: given $x,y$, compute $\gcd(x,y)$.  The fastest algorithm known for this takes $O(T(n) \log n)$ time, where $n$ is the number of bits of $x,y$ and $T(n)$ is the time to multiply two $n$-bit numbers.  It is an open question whether this can be done faster than that, or exactly how fast this is.  A plausible decision problem is: given $x,y,d$, check whether $\gcd(x,y)=d$.  Here it is not known what the fastest possible running time is.  You can check whether $d$ divides $x$ and $y$ in $O(T(n))$ time, so you can check whether $d | \gcd(x,y)$ in $O(T(n))$ time -- faster than we know how to compute the gcd in the first place.  But I don't know of any algorithm to turn this into a way to check whether $d = \gcd(x,y)$ asymptotically faster than computing the gcd from scratch in the first place.  So we just don't know in this case whether the decision problem can be solved faster than the function problem.


Approximation algorithms for an instance of the Monotone circuit satisfiability

If this is a practical problem, rather than an approximation algorithm, I suggest using an off-the-shelf SAT solver.  There are standard ways to encode the constraint that at most $k$ variables are set to true, using an at-most-$k$-out-of-$n$ constraint.  For instance, Z3 has good support for this kind of constraint.
My impression is that approximation algorithms for SAT-like problems tend to perform very poorly.


Non computable problems are also undecidable. Basically undecidable is a subset of non computable.

This is because if you can't even say yes or no then you can't compute it. Take for example the Halting Problem of a Turing Machine, suppose someone asked you after how many steps the Turing Machine will halt on a given input. To answer the exact number you first have to answer whether the Turing Machine is going to halt or not. Then i may count the steps.

What we do is to convert our optimization problem to a decision problem. And if we are not able to give answer of that decision problem we cannot compute it. So, computing is harder than saying yes or no. So if the problem is undecidable then it will be also non computable.


Regex: Any pair of zeros is before any pair of ones

You are correct: the regexp you quote does not match the string $10011$ and that string has the property that every pair of adjacent $0$s occurs before any pair of adjacent $1$s.  But it does match the string $001100$, which fails to have the property!

Your proposed solution matches $11001$ so is also incorrect (the first bracket matches $1$, the second matches $10$, the third matches $01$ and the fourth matches $\epsilon$.

A regexp that does match the required language is
$$0^*(100^*)^*(11^*0)^*1^*\,.$$
It works as follows.

$0^*(100^*)^*$ matches the empty string and any non-empty string that doesn't contain $11$ and that ends with $0$. The string can't contain $11$ because there must be at least one $0$ between every two $1$s.
$(11^*0)^*1^*$ matches every string that begins with $1$ and does not contain $00$, since there must be at least one $1$ between any two $0$s.
Now put the two halves together. If a string has the property that all occurrences of $00$ are before the first $11$, then the section of the string before the first $11$ must either be empty or end in $0$, so it matches the first part of the regexp. The rest of the string contains no occurrences of $00$ so it matches the second part of the regexp.

Note that there are shorter regexps that do the same thing: Yuval Filmus gives $(0+10)^*(1+10)^*$ in a comment to the question. That's a tidier version of the same idea.

And, yes, $(0^*1^*)^* \equiv (0+1)^*$ matches every possible binary string.


Floyd–Warshall algorithm on undirected graph

Every undirected graph can be represented as directed graph by replacing every edge $(i,j)$ with 2 edges $(i,j); (j,i)$. And if you're running Floyd–Warshall algorithm on such directed graph - it would work correctly, as always.


How to draw (intuitively) the first and second principal component in PCA methods?

In the case of 2d data, the first principal component will be aligned along the direction of major continuity, and the second will be perpendicular to that, aligned along the least continuous direction. Generally just the eigen vectors at the mean x / mean y.

Sort of like so (sorry for the poor drawing)

My favorite reference on pca is A TUTORIAL ON PRINCIPAL COMPONENT ANALYSIS by Jon Shlens: pdf His example is in figure 2.

To address your comment:


Automaton recognizing ambiguously accepted words of another automaton

Construct an NFA which will simulate (nodeterministically) two runs of the original NFA on the input. The NFA also remembers one bit – whether the two runs have diverged so far or not. If the bit is off and the NFA chooses two different transitions, then you turn it on. The NFA accepts if both runs accept and the bit is on.

If the original NFA has $k$ states, then the new NFA will have $2k^2$ states. You can convert it to a DFA with $4^{k^2}$ states.

We can reduce the number of states in the corresponding DFA by performing the powerset construction directly. At each step, we will remember, for each step, whether (i) it is impossible to be at that state, (ii) it is possible to be at that state, but there is a unique such run, (iii) it is possible to be at the state, and there are at least two such runs. A state is accepting if there is an accepting states of type (iii), or at least two accepting states of type (ii). This construction uses only $3^k$ states, and so matches your hint.


Proving that the language $\{ w^n\mid w \in \{0,1\}^∗, \, n \ge 2 \}$ is not regular

Suppose towards a contradiction that your language $L$ was regular and let $p$ be its pumping length.
Consider the word $w = 0^p 10^p1 \in L$. By the pumping lemma, $w$ can be written as $w=xyz$ with $x=0^{h}$, $y=0^k$, and $z=0^{p-h-k}10^p 1$ (here $h+k \le p$ and $k \ge 1$) such that, for every non-negative integer $i$, $xy^iz \in L$.
Substituting and simplifying, the above means that, for every $i \ge 0$,  we have $0^{p-k} 0^{ki} 1 0^p 1 \in L$. In particular, the above must hold for $i=0$, implying that $0^{p-k}1 0^p 1 \in L$.
Since $0^{p-k}1 0^p 1 \not\in L$ (recall that $k \ge 1$), this is provides the sought contradiction and concludes the proof.


How to translate automatons (Turing machines) into programs of high level programming language?

https://www.longdom.org/articles/reverse-engineering-turing-machines-and-insights-into-the-collatz-conjecture.pdf is one initial effort to do this for some subclass of Turing machines. Actually there is fantastic culture about it http://bluesky-home.co.uk/. These works almost exclusively cite the author itself, that indicates how undeveloped this field is. Nonetheless, the quality of that research is at the level of peer-reviewed research and the main results are published.


It's true that, in general, definitions don't include the empty string in the set of "terminals", as there's no need for that (e.g. the production rules for a context-free grammar are defined as a relation $V \rightarrow (V \cup \Sigma)^*$ - the star covers all productions of the form $A \rightarrow \epsilon$; in all other contexts, it can be omitted because it has no effect on concatenation).

Note, however, that in the case of a CNF grammar, you couldn't just make a simple convention for "terminals" to include the empty string and cut down to just the first two rules, because rules of the form $A \rightarrow \epsilon$ are not allowed for all non-terminal $A$, just for $S$.


Is CFL closed against exchanging complementation and reversal?

Hint: Show that they are the same language.


Paper-based algorithm to find longest formula which is common to at least two formulas

For each pair of formulas $f_i,f_j$ from your list, find the longest formula common to both $f_i,f_j$.  If things are as in your example, this is as simple as a set intersection.  That gives you $n(n-1)/2$ candidates.  Take the candidate that is the longest.


How to compute function rolling averages maximum for each possible interval length?

The usual approach to compute rolling function is to keep/recompute old data and on each step "add" new data and subtract the data going out of the window. So, you need to transform your sum function into updateSum one:

sum(i+1) = updateSum(sum(i), f(i), f(i+k+1))


Is "capability-based security" vs "hierarchical-protection-domain based security" a false dichotomy?

No.  I don't think that would be a good summary, as it doesn't get to the heart of what I consider important about capability-based systems.  Your rephrasing is putting a focus on how the restrictions are enforced, but that is not the interesting part of capability-based models; the more interesting part is how we express our security goals as capabilities, and what advantages and disadvantages such an approach has.

First off, understand that the notion of capability-based security is not a precisely well-defined concept; it's a broad phrase that could cover multiple possible meanings. Different people use that phrase to mean different things.  So take everything here with a grain of salt.

I suggest that the best way to understand the phrase "capability-based security" is "a security architecture that relies heavily on capabilities".  So, then you need to understand what capabilities are, and why they might be useful.

If you keep reading that Wikipedia article, it contains some explanation of what capabilities are and some ways that they might be useful.

If you want to dive into the details of one particular view on capabilities, I recommend looking at https://en.wikipedia.org/wiki/Object-capability_model and Mark Miller's PhD thesis.  I think you'll find that to have a coherent, principled, and focused view.  It's not necessarily what everyone means when they use the word "capability", but it's one take on the subject that is internally consistent and interesting.


Start by checking that you would be able to build such a NFA if the multiplication table was associative.  That would be a good starting point for you to work on.  (If it's associative, the problem becomes very easy.)  Once you've done that, the next step is:

Now to accommodate the fact that the multiplication table is in fact not associative, and that you want to group multiplications on the right first, you can use the ideas from Louis's comment.  That should make it pretty easy for you to work out an answer to your own exercise, by yourself.


Pointwise mutual information vs. Mutual information?

PMI can clearly be negative, since if $p(x,y)<p(x)p(y)$, then taking $\log \frac{p(x,y)}{p(x)p(y)}$ gives a negative number.

But MI is always non-negative, as it can be written as $d_{KL}(p(x,y)||p(x),p(y))$, where $d_{KL}$ is the Kullback–Leibler divergence which is non-negative (the proof of the latter is not completely trivial).

Intuitively, this happens because if there is a point such that $p(x,y)<p(x)p(y)$, then the probability must "compensate" for this later, with a pair $p(x',y')>p(x')p(y')$.


I'm copying my answer for the similar question - with minimal changes.

The vector equation:
$$P_1 + \alpha * (P_2 - P_1) = P_3 + \beta * (P_4 - P_3)$$
where $P_1 = (x_1, y_1)$ etc., should have a solution, satisfying following conditions:
$$\alpha \ge 0, \beta \ge 0$$
then these two rays $(P_1, P_2)$ and $(P_3, P_4)$ do intersect. However, there are many corner cases here (for example, $P_1 = P_2$ etc.). Also, you can get wrong answers because of the limited precision of your data representation in computer.


Why would we want a self-hosting compiler?

There's no direct technical benefit for a compiler to be self-hosting. If anything, it makes things more complicated, because you have to have a working compiler before you can compile the compiler — the bootstrapping problem. (Solved either by having another implementation of the same language — often an interpreter — or by keeping around binaries of a previous compiler version.)

Compiler writers often like the language that they're writing a compiler for. This is the primary reason why many compilers are self-hosting.

Having a compiler that compiles itself does have an indirect technical benefit: it's a litmus test. A compiler is a complex program. If the language is comfortable enough to write a program in, that's a sign that it's comfortable enough for a large class of programs. If the compiler can compile itself without bugs, that's a sign that it's in a good enough shape to compile other programs with confidence.


To show that any language $L \in NP$ is many one reducible to HP

In fact we can prove something a bit stronger: any language $L$ in NP is polynomial-time reducible to the Halting Problem $HP$.

So let $L$ be a language in NP.
We have a nondeterministic TM $N$ for $L$, which runs in polynomial time.
So
$$
x \in L \iff N \text{ accepts } x
$$
Now $N$ runs in polynomial time --- let's say that on input of size $n$ it runs in time $P(n)$, where $P$ is a polynomial.
Here is an algorithm reducing $L$ to $HP$:

On input string $x$, construct a Turing Machine $M_{x}$ which does the following: "Write $x$ on the input tape, then start trying all possible runs of $N$ on input $x$, in increasing order of size (first try runs of length 0, then runs of length 1, and so on). If a run ever accepts, then halt. otherwise keep running forever.

Now if $x \in L$ then there will be a run of $N$ on input $x$ that accepts, so $M_x$ will halt. And if $x \notin L$, then no runs of $N$ on input $x$ will accept, so $M_x$ will run forever. Thus,
$$
x \mapsto M_x
$$
is a reduction from $L$ to $HP$.
And you may also want to check that the reduction runs in linear time. (That is, the amount of time required to construct $M_x$ from $x$ is linear in $x$.)


What are applications of computational models beyond P?

Not all problems that are encountered in an industrial setting are clearly either NP-Complete or else polynomial-time solvable, even with randomness, heuristics and approximation. So if you encounter (a variant of) a problem such as Exact Independent Set, or Succinct Graph Diameter, for example, then you ought to be looking to the complexity classes $\text{DP}$ and $\Sigma_2^P$. Without the study of these classes, there is no proper placement of these problems, no way to relate them to one another and therefore no way to tackle them coherently, and no way to quantify their hardness. We might look for a way to compactly store and then sell the solutions to NP-Complete problems after we've brute forced them for many inputs. But because of Karp and Lipton, we know that this is impossible, unless the polynomial hierarchy collapses to the second level. In general, these conditional collapses are great for question of the form "Can I...", "No.".

I would love to provide an answer like "We were struggling, but then Immerman and Szelepcsényi proved that $\text{Nondeterministic Logspace}$ was closed under complement, and that really gave a boost to our startup!", being a student myself I don't have any anecdotal evidence, and I would love to hear from someone more seasoned.

So if you are looking for an industrial application of computational complexity theory beyond SAT Solvers, then you may be disappointed. Complexity theory is to computer science a bit like string theory is to physics; it is purely theoretical and its study is not motivated by the urge to solve a particular problem, but rather to understand the nature of computation - how do randomness and nonuniform computation relate to one another? Do all programs with small memory footprints have a fast implementation? - very much like the motivation of theoretical physics is not to design a slightly more efficient engine, but rather to understand the laws of physics. You are taking a theoretical class, and must not be surprised to learn about theoretical results. There are coding classes where you come from; if you prefer those, take those.

If I take the liberty of venturing into speculation, then you may know that right now we do not even know how to rule out ridiculous scenarios in which $\text{BPP}=\text{NEXP}$. Of course everyone believes that the result will be $\text{BPP}\subsetneq\text{NEXP}$, but a proof of this fact cannot come without major advances in our understanding of computation, and, staying with the metaphor of physics, where major advances in our understanding of fundamental physics invariably spurs major progress in unexpected areas, I feel confident in saying that these results, when they come, will spur major progress across all fields of computing.


Resetting Vector clocks in distributed systems

Vector clocks overflow for the same reason that regular integers do. Vector clocks generally maintain a fixed number of bits per process to capture the event count for each respective process. There is naturally a maximum value that each of these bit strings can represent. Any one of these values can potentially be increased beyond their capacity, and thus overflow. For example, if we presume that one process has the following vector clock:
$\vec{P3} = (5, 3, 7) = (101_2, 011_2, 111_2)$
And then $P3$ has an internal event, increasing their event count from 7 to 8:
$111_2+1=000_2$
This number is too large to be represented with only 3 bits. And so the clock overflows back to zero. This will prevent us from properly computing causal ordering in this system, and undermines the consistency of the distributed system.
We can of course allocate many bits to each process to reduce this risk. However, since the vector clocks are regularly passed between processes, we would like to minimise this since it reduces the throughput of communication channels (regardless of whether it is a network, file, shared memory etc).
Therefore we require a mechanism to safely reset clocks within the system, such that we can maintain the constraints of the distributed algorithm. From my understanding this can be done in a few ways:
Blocking Globally
If a process detects that its own counter is about to overflow, it sends a message to every other process informing them to reset their event count for that process on their local clocks. This will halt the distributed algorithm until the process that initiated the reset receives confirmation from every other process.
Consensus Protocols
Depending on how the distributed algorithm is structured, we may not require the full event history to ensure causal ordering for events. Some distributed algorithms have rounds of consensus which allow us to repeatedly incrementally work from a point of stability. These are like rounds in a card game, and offer natural opportunities to reset clocks. This is particularly true of Gossip algorithms. This is very similar to the global blocking algorithm above, but does not wait until an overflow to reset clocks.

There might be some other vector clock reset mechanisms that I am not aware of. It is also possible to organically grow the number of bits used per process as required (which might actually be easiest).
You can read more on these topics with the following academic papers:

Resetting Vector Clocks in Distributed Systems
Randomized Gossip Algorithms


Thompson Regular Expression Search Algorithm 3rd Stage

Let's take the example from the paper: $a(b|c)^*d$. This is first translated into RPN: "$abc|*.d.$". This is compiled into (essentially) an NFA by using a stack. Upon reading a symbol $\sigma$, we push to the stack an NFA for $\sigma$, which we will denote by $N(\sigma)$. Upon reading $*$, we pop an NFA $N(r)$ for the regular expression $r$ from the stack and push $N(r^*)$, an NFA for $r^*$. Upon reading a binary operand $\circ$, we pop two NFAs $N(r_1),N(r_2)$ and push $N(r_1 \circ r_2)$, an NFA for $r_1 \circ r_2$.

Here are the different stages. At each stage, we underline the character being processed, and the resulting stack after processing it, where the top-of-stack is to the right:

$abc|*.d. \qquad $ (empty)
$\underline{a}bc|*.d. \qquad N(a)$
$a\underline{b}c|*.d. \qquad N(a) N(b)$
$ab\underline{c}|*.d. \qquad N(a) N(b) N(c)$
$abc\underline{|}*.d. \qquad N(a) N(b|c)$
$abc|\!\underline{*}.d. \qquad N(a) N((b|c)^*)$
$abc|*\underline{.}d. \qquad N(a(b|c)^*)$
$abc|*.\underline{d}. \qquad N(a(b|c)^*) N(d)$
$abc|*.d\underline{.} \qquad N(a(b|c)^*d)$

Nowadays the regular expression will be parsed into a tree, and the translation process will proceed recursively. If the tree is processed in the correct order (DFS), then this would be completely equivalent to the algorithm described by Thompson.

Either way, having constructed an NFA for the input regular expression, we run it on the input text. This is the part in which we actually search the input text.


I believe you are talking about the Internet and the IP. Here are answers of your questions:

First note the internet is a network of networks. Networks communicate with each other through routers. These big networks are like the ISP, your university or a big organization. Your computer belong to a small network in your ISP subnetwork. This small network is probably your WiFi switch and your computer.

Do hosts find themselves in the routing tables ? NO, but from the IP address of the host and its subnetwork, a router can tell whether they belong to the same subnetwork or not. If they do belong, then there is no need to route the message to another router. The message is simple sent down the subnetwork. You have to study in this case the BGP protocol and the structure of IP.
Your host got nothing to do with routing. The ISP takes care of all that. or your cellular company if you are using your mobile phone .. or etc .. It would be hugely complicated to let these terminals take care of that. Again, you must have a look on the IP structure.
If you try to send a message to X, then your router will look at X (which has an address probably similar to 122.23.12.11 or whatever !) from the upper digits, the router (which is your ISP router in this case) will know which neighbor router to send it to. In general, Internet routing is greedy. How a router selects its neighbors ? [that's another topic]

One advice: dont look to the Internet from a pure theoretical point-of-view.

I guess I answered your question ?


If $n^{\log n}$ is not polynomial or exponential, then what this function is called?

There is no fixed terminology for these types of functions. You might sometimes see "subexponential" or "superpolynomial" used to refer to this kind of behavior.


Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof

I'm not sure your algorithm works. Here is an algorithm that does work: choose $\lceil V/2 \rceil$ random vertices. You can calculate that each edge is chosen with probability at least $3/4$, and so the expected number of chosen edges is at least $3/4$ of all edges.

This algorithm can be derandomized (made deterministic) using the method of conditional expectations. I suggest you read about the method and work the details out. You will get something very similar to the greedy algorithm you're suggesting, but I suspect there will be some subtle differences.


On a semiconductor chip, what state (on/off or read/write) corresponds to conducting or insulating behavior?

In order to understand how physical background of the computers works, you should consider higher-level abstractions of the semiconductors. Otherwise, you will get stuck in a mess of semiconductors. Without basic knowledge of transistors and how these transistors form a logic gate, it will not be easy to comprehend the memory structures and read/write cycles.

To visualize, in CMOS technology, there are two complementary logic structures where one of them is connected to the ground and the other one is connnected to the high voltage source. In rest, these structures are "on" and "off" complementarily. When your output changes, on-off states of them are inverted, thus there are both 'on' and 'off' logic in every case. The scheme is completely different in another technology, let's say PTL.

In the memory case, 'HIGH' and 'LOW' voltages represent immediate memory state rather than individual 'conducting' and 'insulating' states of transistors. If a transistor between low voltage source and your memory output is 'conducting' while a transistor between high voltage source and your memory node is 'insulating', then you have a 'logic 0'. Still, all of them are technology dependent.


Counterexample for LTL - CTL equivalence

Consider the following model: you have 3 states, $s_0,s_1,s_2$ with the transitions: $s_0\to s_0$, $s_0\to s_1$, $s_1\to s_2$ and $s_2\to s_2$ and the labels are $L(s_0)=\{p,q\}$, $L(s_1)=\emptyset$ and $L(s_2)=p$.

Then, every computation starts with $q$, so $Fq$ holds, and every infinite computation eventually gets stuck in $s_2$, or it is $s_0^\omega$, and both satisfy $FGp$, so the LTL formula holds.

However, it never holds that $AFq$, so the CTL formula does not hold.


"Subpaths" of Dijkstra's shortest path also shortest?

Of course, it is true. However, it is not a property of Dijkstra's algorithm but is property of the shortest paths themselves. Suppose that is not true, and you have a shorter path from $C$ to $B$, we denote it as $p_{CB}$. Then we would have a path $A \rightarrow p_{CB} \rightarrow F \rightarrow E$ from $A$ to $E$ which is shorter than $A  \rightarrow  C  \rightarrow  D  \rightarrow B  \rightarrow  F  \rightarrow E$.


The hints you've been given almost work. The important idea is that your guess, $T(n)≤c2^{n/2}$, while correct, doesn't behave nicely in your induction proof, as you noted. What's the problem? Clearly, it's that "$+n$" term in the recurrence, so let's try to make it work by choosing a better guess:
$$
T(n)≤c2^{n/2}−kn \quad\text{for some suitable } k
$$

With this guess, we'll have
$$\begin{align}
T(n)&=2T(n−2)+n\\
&\le 2(c2^{(n−2)/2}−k(n−2))+n\\
&=c2^{n/2}−2k(n−2)+n\\
&=c2^{n/2}−2kn+4k+n
\end{align}$$
and if we can find a suitable $k$ to make this less than or equal to $c2^{n/2}−kn$ we'll be done. In other words, we need to find $k$ such that
$$
−2kn+4k+n≤kn
$$
It's not hard to see that this will happen if
$$
k\ge\frac{n}{n−4}
$$
and this will be satisfied when $k=5$ for any integer $n>4$. Now go back to the inductive proof and recast it for the guess $T(n)\le c2^{n/2}−5n$. You'll find that everything works nicely. Finally, observe that $c2^{n/2}−5n=O(2^{n/2})$ and you'll be done.

This is explained in a bit more detail in this answer to a similar question.


Reducing products in HoTT to church/scott encodings

The standard reference I often give is Induction is not derivable in second order dependent type theory by Herman Geuvers, which says that there is no type

$$N : \mathrm{Type}$$

with functions
$$Z:N\qquad S:N\rightarrow N $$

such that

$$\mathrm{ind}:\Pi P:N\rightarrow \mathrm{Type}.P\ Z\rightarrow (\Pi m:N.P\ m\rightarrow P\ (S\ m))\rightarrow \Pi n:N. P\ n $$

is provable. This suggests that indeed, such an encoding cannot work for pairs as you describe.

The system this is proven for is a subset of the Calculus of Constructions, which contains powerful product types and a universe. I suspect this result can be extended to the system you are interested in, depending on what you have.

Sadly, I don't know the complete answer to your question. I suspect that adding certain parametricity principles "internally" is exactly what is required to make these encodings work with the full induction principle. Neel Krishnaswami, whose knowledge is a strict superset of my own, wrote a paper along these lines with Derek Dreyer:

Internalizing Relational Parametricity in the Extensional Calculus of Constructions

Also of interest is the following paper by Bernardy, Jansson and Patterson (Bernardy has thought deeply about these topics):

Parametricity and Dependent Types

Obviously parametricity has a strong relationship with HoTT in general, but I don't know what the details are. I think Steve Awodey has considered these questions, since the encoding trick is useful in contexts where we don't really know what the eliminators should look like.


Is it incorrect too say that this function problem cannot be in $FNP$?

When we say that an algorithm runs in polynomial time, we mean that its running time is at most a polynomial of the length of the input.  I assume the input is an integer $n$.  The usual way to represent integers is in binary; then the integer $n$ requires $\lg n$ bits to represent.  Therefore, a polynomial-time algorithm will have a running time that is at most $p(\lg n)$, where $p$ is some polynomial.
In each step of computation, the algorithm can output at most one item (e.g., $O(1)$ bits of output).  So, an algorithm with polynomial running time $p(\lg n)$ can output at most $p(\lg n)$ digits of output, for some polynomial $p$.  You can think of this as at most $(\lg n)^c$ digits of output, for some constant $c$ (the constant $c$ will depend on the algorithm).
Now, $2^n$ is asymptotically much larger than $(\lg n)^c$.  So, no, a polynomial-time machine cannot $2^n$ digits, when given $n$ as input.
What if the machine is non-deterministic?  The same is still true.  Non-deterministic means that there are multiple possible branches that the computation could follow.  But for each branch, it's still true that the length of the output can be no longer than the number of steps of computation.  So, each branch of the non-deterministic computation is limited to outputting at most $(\lg n)^c$ digits.
You might be wondering, what is the output of a non-deterministic machine?  Well, that's not a well-defined question.  Instead, for a non-deterministic machine, we can talk about the set of possible outputs.  If it is a polynomial-time machine, then there are a set of possible outputs, but they will all be polynomial in length.  So, a string of $2^n$ digits cannot be among the set of possible outputs; it's too long.
I sense that you are somewhat new to computational complexity.  I suggest that you try to avoid thinking about "function" complexity classes until you are really solid on the "decision" complexity classes.  I find the decision classes easier to think about, and the function classes harder to think about.
Is the problem in FNP?  Well, probably it will be most useful to refer to the definition of FNP.  I'm out of time to look that up right now and check it carefully, but I expect you're going to find that the answer is 'no', because the definition requires (explicitly or implicitly) that the length of the output be at most a polynomial in the length of the input.


Can the encodings set of a non-trivial class of languages which contains the empty set be recursively enumerable?

to complete Raphael's answer, there is an extension of Rice's theorem that says the following:

  Generalized Rice's Theorem

  Let $S \subseteq RE$ be some property, and let $L_S$ be all the TMs that satisfy the property $S$, that is,
  $$L_S = \{ \langle M \rangle \mid L(M) \in S \}.$$
  Then, $L_S \in RE$ if and only if all the following conditions hold:

  for any $L_1,L_2 \in RE$, if $L_1 \in S$ and $L_1 \subseteq L_2$ then $L_2 \in S$.
  if $L_1\in S$ then there exists a finite $L_2 \subseteq L_1$ such that $L_2 \in S$.
  The language of 'all finite languages in $S$' is in RE.  (in other words, there exists a TM $M_S$ that, if $L$ is a finite language $L=\{w_1, w_2, \ldots w_k)$, and $(w_1, w_2, \ldots, w_k)$ is given to $M_S$ as an input, $M$ accepts only if $L\in S$.

Now back to the original question. We now that $\langle M_{loopy}\rangle\in L$ so $L(\langle M_{loopy}\rangle)\in C$. But $L(\langle M_{loopy}\rangle)=\emptyset$ since this TM never halts. This means that $\emptyset \in C$.

Now lets look on the first condition of the above theorem. ANY language $L$ satisfies $\emptyset \subseteq L$. Thus in order to satisfy condition 1, it must be that $C=RE$. However, the question states that $C\subsetneq RE$ and therefore, by the theorem, $L\notin RE$.


For a nondeterministic decider the answer is At-least one "copy" halts on a "yes"/"no" state; copy-paste from another answer:

for a Nondeterministic Turing machine (NDTM) processing an input $x$ there can be infinite computations (paths); some of them will halt on the accept state $q_Y$, some will halt on the reject state $q_N$, some will run forever;

a string $x$ is accepted by a Nondeterministic Turing machine if at least one of its computations halts on the accepting state $q_Y$;

we say that "$M$ accepts $x$ in $m$ steps" if $M$ accepts $x$ and $m$ is the length of the shortest accepting computation on input $x$;

a language $L_M$ recognized by a NDTM $M$ is the set of $x$ accepted by $M$ (this is independent of whether $N$ is a decider or not);

the definition of time complexity for a Nondeterministic Turing Machine $M$ is slightly different from the definition of time complexity for a Deterministic Turing Machine:
$T_M(n) = max ( \{1\} \cup \{ m \; : \; $ there is an $x \in L_M$ such that   $|x|=n$ and $M$ accepts $x$ in $m$ steps $\})$

we say $M$ is a decider if $T_M(n)$ is computable.

See Garey&Johnson, "Computers and Intractability"


What are some research papers or techniques that deals with fitting clothes on a human?

I would expect most of the works use Generative Adversarial Networks (GANs) for this because they are powerful generative models capable of learning the complex underlying probability distribution.

In this amazing work the authors used a Conditional GAN, in which they can generate an image conditioned on semantic segmentation map. In your case, you might want to condition on two images, one of a dress and the other of a human. https://github.com/NVIDIA/pix2pixHD

You might also want to look at the ICCV 2019 workshop on fashion.


No, one can't achieve a better approximation ratio for your problem.  This follows by a simple padding argument.

Let $S_1^*,\dots,S_m^* \subseteq S^*$ be an instance of ordinary set cover (where the sizes of the sets are not restricted to be the same).  Let $n = |S|$.  Define $S^* = S \cup \{1,2,\dots,n\}$ where it is assumed that $1,2,\dots,n$ represent $n$ new symbols not found in $S$.  Also define $S_i = S^*_i \cup \{1,2,\dots,n-|S^*_i|\}$ and $S_{m+1} = \{1,2,\dots,n\}$.  Then $S_1,\dots,S_m,S_{m+1} \subseteq S$ form an instance of your uniform set cover problem; by construction, the sets $S_1,\dots,S_m$ all have the same size.  Moreover, the minimum cardinality cover for the original problem $S^*$ differs in size from the minimum cardinality cover for the uniform problem $S$ by at most one, since given any solution $\{i_1,\dots,i_k\}$ for the original problem we obtain a valid solution $\{i_1,\dots,i_k,m\}$ for the uniform problem, and vice versa, any valid solution for the uniform problem is also a solution for the original problem.

It follows from this reduction that uniform set cover has the same approximation factor as ordinary set cover.  Thus, all the standard approximability results for set cover carry over to your problem as well.


Formal languages: constructing * for a linear set

Hint. It suffices to observe that if $L = \{ v_0 + c_1v_1 + c_nv_n \mid c_1, \dotsm, c_n \in \mathbb{N}\}$, then $L^* = \{ c_0v_0 + c_1v_1 + c_n  v_n \mid c_0, \dotsm, c_n \in \mathbb{N}\}$.


Oh my word! Coding that did take a while. The logic however, is quite simple. Recall the number system.

First, determine the length of the number entered by the user. You can do so by dividing the number repeatedly by 10 until the quotient becomes zero.
Then, the maximum value of a digit in decimal number system is 9. So compare each digit in the number with 9. The modulo division operation comes handy in here. See if there's a match. If there's no match go to the next smaller digit, 8 and continue this until you get to zero.
Multiply the first match found using this procedure with 10^(length-1) i.e. you are making it your most significant digit (number systems)
Reduce the length length--
Continue this procedure until length becomes zero
A little tip for efficiency, note down the matched digit each time and make that the slab for comparing the remaining digits in the number i.e. if you found out 5 is the first match, and thus the greatest digit found in your number, there's no point starting your comparisons from 9 again for the next digit. Start at 5. Don't be overly smart and start at 4 though. Remember there can be multiple 5's in a number.

I wrote a working piece of code for this. So this algorithm works. Hope that helps. Ways to improvise the performance are appreciated. However, don't suggest the usage of arrays or strings as they are forbidden in the question.


Computing the number of bits of a large power of integer

[edit] As suggested, I edit my answer to give more details.

The answer to my second question is no:

Proposition. Computing $\log(x)$ up to precision $k$ is at least as hard as computing the bit-size of $x^{2^k}$.

Proof. Let $|y|$ denote the bit-size of an integer $y$. First notice that for a nonnegative integer $y$, the bit-size of $y$ is $1+\lfloor \log y\rfloor$.

Thus, $\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$. Now $2^k\log(x)$  is $\log(x)$ shifted $k$ positions to the left. Thus one can compute $\log(x)$ to precision $k$ by simply subtracting $1$ to the bit-size of $x^{2^k}$ and shifting the result $k$ positions to the right.


Cube 3x3: Using just face rotations, transform the cube from configuration A to B

If the number of "don't care" colours is large, as it is in this example, you probably can't do much better than A* search.
One simple heuristic function is the minimum number of moves required to move the currently-least-correct piece to its correct position. Since you're willing to tolerate some non-optimality, summing over all pieces that are not in their correct locations will probably do quite well in practice.


Is relation following given characteristic already in 2NF, 3NF and BCNF?

Consider a relation schema R(A, B, C), with the functional dependencies:

A → B
B → C

In this schema there is only one candidate key (A), and it has a unique attribute. But the schema is not in BCNF, since B is not a superkey, neither in 3NF, since C is not a prime attribute.

So your intuition is correct.


This looks like a directed graph. For a Python graph library, you can have a look at networkx. There are other libraries too, like igraph and graph-tool.


Basic Idea

For small values of n insertion sort runs faster than merge sort . Hence insertion sort can be used to Optimize merge sort

Basic idea is apply insertion sort on sublists obtained in merge sort and merge the sorted (using insertion sort) lists

Coming to Question
Base Condition
If each word is 4-byte long, then a 128-byte cache contains 32 words. Therefore, if the problem size is 32 or less, the instance will be immediately solved by Insertion Sort, otherwise it will be split in two sub-problems with the same size, which will then have to be merged
Time Complexity

Total Complexity = Complexity Insertion Sort + Complexity of Merge Sort

We have $n$ elements . We are dividing it to $\frac{n}{x}$ sublist each contain x elements each

Complexity Of Merge Sort

Total work done by merge sort in copying $n$ elements from each level to upper level is $O(n)$
Number of levels = number of sublists or small problem = $O(\log \frac{n}{x})$
Complexity of Merge sort : $O( n \log \frac{n}{x} )$

Complexity Of Insertion Sort

We are sorting $ \frac{n}{x} $ lists each of $x$ elements using insertion sort so complexity contributed by insertion sort is $\frac{n}{x} $ INSERTION ${x}$

Total Complexity =  $\Theta ( \frac{n}{x}  \ \text{INSERTION} \ (x)  +  n \log \frac{n}{x} )$

Best Case

is when Insertion sort perform in best case with $O(n)$ ie $\text{INSERTION} \ (x) = x$
Best Case Complexity=Total Complexity =  $\Theta ( n  +  n \log \frac{n}{x} )$

Worst Case

is when Insertion sort perform in best case with $O(n^{2})$ ie $\text{INSERTION} \ (x) = x^{2}$
Best Case Complexity=Total Complexity =  $\Theta ( nx  +  n \log \frac{n}{x} )$

More Information : Gate Overflow - Sorting Algorithm


$\Theta(2^k \lg n)$ queries are necessary and sufficient.

Algorithm

Define $I = \{i_1,\dots,i_k\}$.  Our goal is to recover $I$.  Given $x$, define $Z(x) = \{i : x_i = 0\}$.  For each $x$ where $f(x)=0$, we learn that $Z(x) \subseteq I$.  This suggests the following algorithm:

Set $J := \{1,2,\dots,n\}$.
For each $x$ in the input such that $f(x)=0$, set $J := J \cap Z(x)$.
Output $J$.

Analysis: It's guaranteed that this algorithm will output a set $J$ satisfying $I \subseteq J$.  Can we ensure that $I=J$?  Well, if we have $c \lg n$ values of $x$ where $f(x)=0$, then for any fixed $j \notin I$, $\Pr[j \in J] \le 1/2^{c \lg n} = 1/(2^c n)$; then by a union bound, $\Pr[J \ne I] \le 1/2^c$.  So, the probability that this produces the wrong output can be made exponentially small in $c$, as long as we have $c \lg n$ values of $x$ where $f(x)=0$.

Moreover, given $m$ pairs, we expect $m/2^k$ of them to have $f(x)=0$.  So, if we have $c \cdot 2^k \lg n$ pairs, we expect $c \lg n$ where $f(x)=0$.  Therefore, $O(2^k \lg n)$ pairs suffice to ensure that this algorithm will give the correct answer (except with negligible probability of failure).

Lower bound

This is the best we can do.  We can extend the information-theoretic lower bound in the question.

Let's start by showing that $\Omega(2^k)$ pairs are needed.  For a random $x$, we have $\Pr[f(x)=0] = 1/2^k$.  Therefore, we obviously need $\Omega(2^k)$ pairs to have a good chance of observing at least one pair where $f(x)=0$.  With $o(2^k)$ pairs, there's an overwhelming probability that all pairs satisfy $f(x)=1$, in which case we have learned nothing about $f$.  So, $\Omega(2^k)$ pairs are needed.

We can improve this lower bound a bit.  Call $x$ good if it satisfies $f(x)=0$.  Suppose we have to examine $p$ pairs before we see the first good value of $x$.  Once we see our first good value of $x$, how many bits of information have we learned about $f$?  Only $\lg p$ bits (because one of those $p$ pairs yields 0 and all the rest are 1; there are $p$ ways to select one of them to be 0).  It takes about $2^k$ pairs to see the first good value of $x$.  So, after observing $2^k$ pairs, we expect to learn about $k$ bits of information about $f$.  In general, each good value of $x$ gives us about $k$ bits of information about $f$, and we need to see about $2^k$ pairs per good value obtained.  Now as described in the question, we need $\Omega(k \lg n)$ bits to specify $f$ uniquely.  Therefore, we need $\Omega(\lg n)$ good values of $x$, so we need $\Omega(2^k \lg n)$ pairs in total.

This gives a lower bound that matches the performance of the algorithm above, to within a constant factor.  Therefore, the algorithm above is asymptotically optimal.


Your cache is direct mapped so there are no sets. Those are set associative caches.

In your example the tag is 26 bit, block 4 bit and byte offset is 2 bit.

To get that just break your 32 bits into tag, block and byte fields.
16 blocks means 4 bits to address a block.
4 byte blocks means 2 bits to address bytes within blocks.
Rest of the bits are 26, which is the tag.
When you convert 0xC4001234 to binary and remove first 26 bits and the last 2 bits that gives you the 4 block bits.

In your case it is 1101 or block 13 of 0-15.


Branch Prediction - LOCAL BHR without tag

The 1024 entries would be indexed by bits from the instruction address, so the history is likely to be for the same branch (especially since there is temporal locality in instruction execution, so the same branch is more likely to be executed nearby in time than some other branch that happens to have the same index in the branch predictor). Without complete tags, there is the possibility of aliasing (where the history at a given index is actually from a different branch than the instruction address being looked up), but since only a prediction is provided even destructive aliasing would only cause a misprediction. With 32-bit addresses and fixed-length 4-byte instructions, 1024 entries would use 20 bits per entry for complete tags, requiring over six times as much storage as an untagged table with 3 bits of history per entry.

(Aliasing can reduce prediction accuracy enough that techniques like agree predictors have been developed to reduce destructive aliasing. In an agree predictor a second source of prediction information [usually static for a per-address predictor, often a dynamic per-address table for a global history based predictor since adding the per-address table also allows tournament prediction] provides a bias for the other predictor; instead of predicting taken or not-taken, the other predictor predicts agree or disagree. Bi-Mode prediction is similar, but uses two tables with table selection based on the branch bias.)

For a local history predictor there can also be aliasing in the table translating the local history into a prediction. If only one table is used one branch's behavior could interfere with predictions for another branch. (This is not a terrible design; the Alpha 21264 used a 1024-entry local history predictor with 10 bits of history and a single shared 1024 entry [indexed by the 10 history bits] predictor with 3 bit saturating counters, along with a global predictor and chooser.)

Using tags (even partial tags) allows the use of associativity and the percentage storage overhead is less if the branch target buffer is merged with the local predictor. (A unified direction predictor and branch target buffer would generally have fewer direction entries than separate predictors and BTB entries for unconditional control flow operations do not need direction prediction.) However, direct-mapped structures are faster (and using tags increases energy use), so there are tradeoffs.

(Similar tagging tradeoffs exist for bimodal [distinct from Bi-Mode] predictors, where a single table indexed by a hash of the branch address provides the prediction, typically using either a two bit saturating counter or a prediction bit and a hysteresis bit.)


What do these arrows in design pattern diagrams mean?

The arrows mean distinct things. This is a UML (unified modeling language) diagram. Rules for reading and writing these diagrams are pretty well-established, and you should be able to look up some references.

In that diagram, the hollow arrow means generalization (i.e., inheritance, IS_A), and the hollow diamond means aggregation (i.e., a kind of association, HAS_A). The dotted line connects a comment/label and contains auxiliary/meta information (I believe, but double check this one).


Confused b/w non-deterministic finite state automata vs finite state automata

The automaton in the image is indeed nondeterministic.

You need to think a little differently about nondeterministic machines. It's no longer a question of "what happens when X?" but about "what can happen when X?". For each input, there can be many different computations, even with different outcomes.

Note how the definition of acceptance is different. For DFA, it's "the (unique) computation is accepting"; for NFA, it's "there exists an accepting computation".

Here, in your example, if the input is "twenty", there are two computations:

$q_0 \to q_1$ and
$q_0 \to q_2$.

Since the second is accepting, "twenty" is in the language of this automaton.

Side note: A TCS book that uses twenty as terminal symbol and generally avoids LaTeX for it's mathematics typesetting is highly suspect. I recommend that if you run into any problems, look for a standard textbook before worrying too much.


That depends on how pedantic you are. Morally and semantically speaking, every DFA is an NFA in which there is a unique arrow exiting every state for every character in the alphabet, and there are no $\epsilon$ transitions.

Syntactically speaking, it depends on your definition: the transition function could be encoded differently, so that the transition function of a DFA might not be "legible" for an NFA simulator.

I would not worry too much about the syntactic viewpoint.


n-state DFA that requires n-2 steps to check equivalence

Consider the following DFA on the alphabet $\{0\}$:

The states are $q_1,\ldots,q_n$, with $q_1$ initial and $q_n$ final.
$\delta(q_i,0) = q_{i+1}$ for $i < n$, and $\delta(q_n,0) = q_n$.

Consider the pair of states $q_1,q_2$. For $i < n-2$, $\delta^*(q_1,0^i),\delta^*(q_2,0^i) \notin F$, whereas $\delta^*(q_1,0^{n-2}) = q_{n-1} \notin F$, $\delta^*(q_2,0^{n-2}) = q_n \in F$.


Yes, they are the same languages: $L=L'$ (at least the way that I understand the definition of $L$).  We say that the grammar $G_1$ can parse a string $x$ iff $x \in L(G_1)$.  It follows that $L=L'$.  $L$ is defined in a somewhat informal way; good for you for finding a way to provide a more precise formal statement of it.

Indeed, the problem of deciding whether two CFLs have a non-empty intersection is undecidable, so neither $L$ nor $L'$ is decidable.


How to construct a sequence of polynomial-time Turing machines

The simplest way is to use timed Turing machines. We enumerate pairs $\langle T_i, P_j \rangle$, where $T_i$ goes over all Turing machines, and $P_j$ goes over all polynomials. The machine corresponding to $\langle T_i, P_j \rangle$ simulates $T_i$ for $P_j(n)$ time steps, and then stops it (unless it already halted).

This is better than your solution, since you have to verify that the given Turing machine runs in time $P(n)$ for some given polynomial, a task which is uncomputable.


Does the host operating system know the content of your messages in a messaging applications?

If the OS is malicious or compromised, it can monitor everything you're sending or receiving.  As one simple example, it can monitor every key press, every mouse event, and everything displayed on the screen.  Why?  Because the OS runs at ring 0, it has control over everything else.


Algorithm for Filling Regions with Small Gaps

This is clossing operator implemented as dilate-then-erode filter and then it is FloodFill.
Dilate filter is adding pixels that would became new hull.
Erode filter is cutting out pixels that are at the hull.
Here is try me link: Demo of operators
One thing that could be improved in this technique are gaps after filter.

You can get rid of it by applying dilation on color region.

This is one kind of solving, another would be to go along the edge and find pattern edge-gap-edge with given radius.
There are also caveats - if edge is not in single color, then operators must include that information or get binary representation (with binary data, e.g. 0 means empty, 1 means edge).
Clossing operator is easy to implement but slower than contour tracing.
You could trace edge by FloodFill starting from edge region, using BFS and going into counting mode after boundary is crossed, to check within gap radius.


There are two types of Post tag systems: with halting symbols, and without.

A Post tag system with a halting symbol gives its output in the same way that a standard Turing machine does: on the tape. Whatever is written on the tape when it hits the halting symbol is its output.

A Post tag system without a halting symbol is a bit trickier. It only halts when the tape has too few symbols left to do another step of processing. So there's no way to give any output on the tape. Thus, its output is the sequence of intermediate states the system has been in in the process of producing the result.

The Wikipedia article you linked gives an example of this: a halting-symbol-less 2-tag system to compute the modified Collatz sequence.


Use Dijkstra to find negative cycles in a graph

No, it won't work.  If your graph has a negative weight edge and Dijkstra computes the shortest paths wrong, then it might be possible to relax an edge (to make the shortest paths correct) even though there is no negative-weight cycle in the graph.


What is the implication of NP-completeness if P=NP?

Yes, but without further information, only that $X$ has a lower bound of $\Omega(n^{2})$. (I'm assuming that, in line with the title, you're interested in what happens if it turns out that $P=NP$) The problem with transferring this information elsewhere is with the reductions used. As the only constraint is that they're computable in polynomial time, we can easily have the case that we simply solve the problem as part of the reduction (again assuming $P=NP$), so we can reduce it to any other problem in $P$ (this is why $P$-completeness is defined using more restrictive reductions - $NC$ reductions or logspace reductions, or similar, depending on exactly what version you're going for).

With some more specific information we can say something. If we have a problem $W$ where $X \leq_{P} W$ and we can compute the reduction in $O(n^{c})$ where $c < 2$, then we know that $W$ has a lower bound of $\Omega(n^{2/c})$ essentially because an upper bound on the problem tells us something. Say $A$ has an upper bound of $O(n^{c_1})$ for some $c_1$, we have a problem $B$ such that $B \leq_{P} A$ and we can compute this reduction in $O(n^{c_{2}})$, then $B$ has, at worst, a $O(n^{c_{1}c_{2}})$ algorithm - at worst we can convert the instance of $B$ to an instance of $A$ and solve that instead. So in our case, if $W$ had an upper bound of $O(n^{2/c - \varepsilon})$ for any $\varepsilon > 0$, then $X$ could be solved in $O(n^{c\cdot (2/c - \varepsilon)}) = O(n^{2-c\varepsilon})$, contradicting the lower bound.

Note of course that none of this really has anything to do with $X$ being $NP$-complete, it's true for any problem in $P$.


Understanding the definition of a language

The expression "$a_i = a_{i+1}$" means "$a_i$ and $a_{i+1}$ are equal".
Presumably $a_i$ is a symbol, that is, $a_i \in \{0,1\}$. Therefore the condition states that $a$ contains at least four symbols, and there are two adjacent symbols which are equal, that is $a$ contains either $00$ or $11$ as a substring. Stated differently, $a$ contains at least four symbols and it doesn't consist of alternating zeroes and ones (i.e. you are not allowing 0101, 01010, ... or 1010, 10101, ...).


How to generate a number which is divisible by all numbers in a given range?

The number you see is known as the least common multiple.


If you plug in the result in what is returned by the recursion, you get:
$$\frac{n!}{(n - \lfloor \frac{m}{2} \rfloor)!}
\frac{(n - \lfloor \frac{m}{2} \rfloor)!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!}
= \frac{n!}{(n - \lfloor \frac{m}{2} \rfloor - \lceil \frac{m}{2} \rceil)!}$$

You can see the right side is equal to $\frac{n!}{(n - m)!}$ because of the identity $m = \lfloor \frac{m}{2} \rfloor + \lceil \frac{m}{2} \rceil$ (if you are in doubt about this: check the cases $m$ even and $m$ odd separately).

For correctness, the only thing left to check then is the base cases $m=0$ and $m=1$ are correct (which is a trivial observation), that Falling is not invoked with incorrect parameters (this is the case if $m \le n$ holds) and that it terminates (also the case because the invoked instances have strictly smaller parameters).


Context-free grammar how to have same number of variables within a language

Your approach won't work. Whenever you try to match the length of two non-terminals, that should be a big red flag your approach won't work.

Here's a hint: expand from the middle out, after starting with $S = a \mid b \mid aAa \mid bBb$. Can you take it from here?


Proving that Turing decidable languages are closed under reversal

Suppose that you have a Turing machine $M$ that accepts a language $L$.
Construct a new Turing machine which, on input $x$, reverses its input and then passes control to $M$. The new Turing machine accepts the reverse of $L$.


How to implement two stacks in one array?

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.


If I understand you correctly, the following comment seems to get to the heart of what you're really asking:

  A regular language is one where you can make an automata for it, or a regular expression for it. But this seems like a poor definition to me because how do you know if none exist or you just haven't been able to think it up yet?

That's a fair question.  I'm afraid the answer is -- the definition is what it is.  Whether you consider it poor or not, this is the standard definition of a regular language.  For now, I recommend that you simply accept it and work within it.  I agree that the implications are a bit.. uncomfortable.  Unfortunately, that's life.

Many definitions are like this.  For instance, consider the definition of what it means for a number to be prime: a number $n$ is prime if there it does not have any divisor $d$ such that $1<d<n$.  Of course you can ask: how do you know if such a divisor exists?  Maybe you just haven't been able to find one yet?  The answer is that you might not know... but that's still the definition, and there are good reasons to use this definition, rather than some other.

Ultimately, there are reasons why the standard definition of regular languages is useful.  Those reasons might not be obvious when you are first starting to study the material.  From a computer scientist's perspective, one reason why the notion of a regular language is useful is that it corresponds to what can be accepted by an automaton with finite state, and this has many applications through computer science (parsing by compilers, model checking, and more).  From a mathematician's perspective, the notion of a regular language is interesting because it has many useful properties.

But for now... accept that the definition is what it is, and there are reasons for it to be that way, and go with it.


Push down automata acceptance by Empty stack and final state

Yes, that is possible. If you start with one that accepts by final state, you can change that one into an automayon that accepts by final state and empty stack as follows.

First create a new final state $f$. From every old final state have an epsilon transition to the new state $f$. Add transitions to $f$ that empty the stack.

It seems best to keep the old final states. A computation of the old automaton might end in one of the old final states with an empty stack, in which case it should be accepted, but we have no contents of the stack, so we cannot move to $f$.


Finding a language that is $NP^L$-complete

What you are looking for is a relativization of the Cook-Levin theorem in the sense that you consider SAT and NP relative to an oracle for $L$. You can find the answer to that in this answer, point number 2. There you get (an extension of) Circuit-SAT as a complete language; reducing this to your version of SAT should not be too hard.

Note that, as mentioned in the linked answer, this is a bit different than a relativization in the sense that it is the reduction which possesses an oracle for $L$.


Guarantees on computing $a+x(b-a)$ in floating point

Here is a proposed alternative
$$f(x,a,b) = \operatorname{ifelse}(x<0.5, a+x(b-a), b-(1-x)(b-a))$$
which also satisfies (a) and (b), but it is not accurate near $0.5$. It also satisfies (c) except maybe at $\operatorname{prev}(0.5)$ and $0.5$.

For example with double-precision arithmetic we compute $f(0.5,-1.0,\operatorname{prev}(1.0))$ to be -1.11e-16 but it is actually -5.55e-17, so out by a factor of 2.

It's worth noting that the implementation proposed in the question gets this example correct.


When $new\subseteq clauses$ then, if we continued, the next line would be $clauses \leftarrow clauses\cup new$ but $clauses\cup new = clauses$ so we'd be doing the exact same calculation the next time through the loop deducing nothing new and looping forever.

The point is, if we "resolve" all pairs of clauses and deduce nothing new, then we've derived all the consequences from the original set of clauses. If we still haven't derived a contradiction at that point, then $\neg\alpha$ is consistent with $KB$ and thus $\alpha$ is not provable. This last isn't necessarily completely accurate either, as it only shows that $\alpha$ is not a propositional consequence of $KB$. For example, if $KB$ was $\forall x.P(x)$ and $\alpha$ was $P(t)$, then $\alpha$ is provable from $KB$ but not via propositional reasoning.


Dynamic connectivity in forests with constant query time

An Euler tour tree is a linear representation of a tree. When the tour is stored in a balanced binary search tree keyed (implicitly) by the index in tour, the update and query operations can be done in $O(\log n)$. This is described in the referenced Erik's notes.

The tour can be stored in a two level array (similar to the structure described in section 2.2 of Data Structures for Traveling Salesmen). Each tree tour is stored in $O(\sqrt n)$ arrays with $O(\sqrt n)$ elements in each. Each tour element keeps a reference to its array, and each array keeps an reference to its parent array.

The update operations involves a constant number of arrays so it can be done in $O(\sqrt n)$. The query operation can be done in $O(1)$: The root of the tree containing each element is found and then compared. Each root is found in the position 0 of the first array of the tree tour. To find the tree tour containing a element just follows the element reference to its array and then follows the link to the parent array (that is, the tree tour).


Proving that PP is closed under symmetric difference

As stated in the Wikipedia article about PP, a proof that PP is closed under symmetric difference was a PhD thesis by David Russo Structural properties of complexity classes. Proving that PP is closed under union was also open for a long time until it was answered by R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991


Is it computable if a particular number follows the Collatz conjecture?

In short: we don't know :-)

There is a ((very) little) chance that the Collatz sequence is Turing complete (with probably some caveats like in the case of Two-counter Machines); i.e. there is an algorithm which for every turing machine $M$ outputs an $x$ such that:

$Collatz(x)$ is on a divergent trajectory if and only if $M$ doesn't halt on empty tape

in other words "deciding if a particular Collatz trajectory is divergent" could be undecidable.


Uniqueness of non-dominated two-dimensional points

For $n=1$ the statement is trivially true. Otherwise $n > 1$.

Sort the points in each dimension in ascending order. Let $r^i_1, r^i_2$ be the rank of point $i$ in each dimension, rounding ties down. (Thus if there is a duplicate value (1,2,2,3) we take the index of the first appearance in the list). We use 0-based indexing.

First we note that for a point $p_i$ that $w_i = r^i_1 + r^i_2$ gives an upper bound on the number of points that can't dominate $p_i$. Therefore, by a counting argument, if $w_i < n-1$ there must be a point that dominates $p_i$.

We will now assume that we have a set of points that doesn't have a dominated pair. For convenience, we rename all the points such that they are ordered in the first dimension, thus $p^0_1 \leq p^1_1 \leq \dots p^{n-1}_1$.

We will now prove that $r^i_1 = i$ and $r^i_2 = n - 1 - i$.

Clearly $r^0_1 = 0$. Therefore, $r^0_2 = n-1$, otherwise $w^0 < n-1$, and there is a point dominating $p_0$. Since $r^0_2 = n-1$ there is no point having the same value in the second dimension (otherwise, $r^0_2 < n-1$).

Assume that we have proved for the first $j$ points, we now prove for $j+1$. Note that since each of the first $j$ points have $r^i_2 = n-1 - i$, this means that there are no other points having those rankings. Since the points are in ascending order in the first dimension, $r^{j+1}_1 = j$ or $r^{j+1}_1 = {j+1}$. Let us assume by contradiction the former. Therefore, since there are no dominated pairs, we have that $r^{j+1}_2 \geq n - 1 - j$, which is a contradiction (to no other points having those rankings). Therefore, $r^{j+1}_1 = {j+1}$ and since there are no dominated pairs, $r^{j+1}_2 = n - 1 - {j+1}$, and no other point may have that value.


If $F$ is continuously differentiable and smooth, you can use the gradient to walk along the contour.  In this way you could walk on the contour starting at $x_1$ (tracing both directions of the contour) and see if you reach $x_2$.

In particular, if you're currently at a point $x \in \mathcal{C}$ on the contour, then the gradient $\nabla F(x)$ tells you what direction to walk if you want to stay on the contour: you should walk in the direction $(\nabla F(x))^\perp$, where we define $(a,b)^\perp = (b,-a)$.  (In other words, you should walk in the direction perpendicular to the gradient.)  In particular,  when $\epsilon$ is sufficiently small, $x + \epsilon \cdot (\nabla F(x))^\perp$ will be approximately on the contour.  This is because $\nabla F(x)$ points in the direction that most increases $F$, and if we're on a contour and the contour is a line, $\nabla F(x)$ points in a direction perpendicular to that contour.   (See, e.g., https://math.stackexchange.com/q/599488/14578.)

So in principle if the contour was a simple line (whether closed or open), the following would be sufficient: start at $x_1$ and walk in one direction and see if you eventually reach $x_1$.  In parallel, start at $x_2$ and walk in the other direction and see if you eventually reach $x_2$.

In practice there are two complications.

First, the contour is curved, so the gradient only helps you walk in a direction that is approximately along the contour -- but maybe not exactly.  So, I suggest a refined way to walk at the contour.  At you're currently at the point $x$, first to the point $x' = x + \epsilon \cdot (\nabla F(x))^\perp$.  The point $x'$ might not be exactly on the contour, but it'll probably be close.  Next, use gradient descent starting at $x'$ to find a point on the contour that is close to $x'$.  If $F$ is everywhere positive, you might do this by minimizing the objective function $\Phi(x'') = F(x'') + c \cdot \|x''-x'\|^2$ where $c>0$ is a sufficiently small constant; otherwise, you can use $\Phi(x'') = F(x'')^2 + c \cdot \|x''-x'\|^2$.  If you have a better way to find the nearest point on the contour, go ahead nad use that.  Finally, walk to this point $x''$.  This gives you an adjacent point on the contour, that's approximately distance $\epsilon$ away from where you started.  Repeat this.

The second complication is that the contour might not be a simple line; there might be places where two or more lines meet at an intersection.  At this point, $F$ won't be differentiable and the gradient might not be computable or meaningful.  You'll have to figure out how to detect that situation; perhaps you can use your domain knowledge about $F$ to help you detect that.  If you have no other ideas, one possibility is to pick a dozen random points in the neighborhood of $x$, project each one to the nearest point on the contour, check the gradient, and see if all of them seen consistent with a single nearly-straight line or whether their appear to be multiple lines converging.  Once you detect an intersection point, you can use depth-first search (basically, explore all directions out of the intersection point) to traverse the connected component -- then it reduces to the problem of checking whether two vertices in an undirected graph are in the same connected component, and that can be done using DFS.

This uses techniques that are quite similar to that proposed in my answer to your previous question on a 3D version of this situation.


In the Data Link Layer, is it better to use large or small frames?

Bigger frames mean a higher useful data fraction (same header size, more payload). But bigger frames mean a higher probability of the frame getting corrupted by random errors (thus getting lost). Larger frames mean higher latencies (need to wait for all of it to arrive, be checked, and handed to the application to be able to use any data in it). They also mean larger buffers might be a problem in limited devices).

As you can see, frame size is an exercise in compromise among a host of conflicting desirable measures.


The only permutations who satisfy this condition are the identity and its inverse (as string inverse), $\pi(i)=n-i+1$.

Note that $1$ has to be in one of the edges (if it has two neighbors, then at least one of them is bigger  than $2$ and the condition is not satisfied). Placing $1$ in the left edge forces the entire permutation to be the identity, and placing $1$ in the right edge forces the permutation to be its inverse.


Given a list of integer rectangle areas, find all integer rectangles that they can tile

This answer assumes that you only allow the tiles to have integer sides.
There are always some trivial tilings, in which the rectangle being tiled has either a single row or a single column. Counting the number of these is simple combinatorics. Let us show that deciding whether there are any other tilings is NP-complete (under randomized reductions, or assuming some number-theoretic conjectures). It is clearly in NP. To show that it is NP-hard, we reduce from PARTITION. An instance of PARTITION is a multiset of positive integers, and the problem is to determine whether it can be partitioned into two multisets with equal sum.

We start by showing that PARTITION is NP-hard even if all parts are odd and the total sum is divisible by 4. Let us first ignore the latter requirement. Given an instance $S = \{x_1,\ldots,x_n\}$ of PARTITION, construct an instance of the new problem with $S' = \{2nx_1+1,\ldots,2nx_n+1\} \cup \{1^n\}$ (here $1^n$ mean $n$ many $1$s).
If the original instance can be partitioned into two equal parts, say $\{x_1,\ldots,x_m\}$ and $\{x_{m+1},\ldots,x_n\}$, then so can the new instance. Indeed, consider the multiset $\{2nx_1+1,\ldots,2nx_m+1\}$, together with $n-m$ many $1$s. This multiset sums to $2n(x_1 + \cdots + x_m) + m + (n-m) = 2n(x_1 + \cdots + x_m) + n$. Similarly, the remaining numbers sum to $2n(x_{m+1} + \cdots + x_n) + (n-m) + m = 2n(x_{m+1} + \cdots + x_n) = n$, which is identical.
Conversely, suppose that $S'$ can be partitioned into two equal parts, say one of them consisting of $2nx_1+1,\ldots,2nx_m+1$ together with $r$ many $1$s. It follows that
$$ 2n(x_1 + \cdots + x_m) + m + r = 2n(x_{m+1} + \cdots + x_n) + (n-m) + (n-r), $$
and so
$$ 2n(x_1 + \cdots + x_m - x_{m+1} - \cdots - x_n) = (n-2m) + (n-2r). $$
Since $1 \leq m \leq n-1$ and $0 \leq r \leq n$, the right-hand side is in the range $[-(2n-2),(2n-2)]$. Since the left-hand side is a multiple of $2n$, we conclude that the right-hand size is zero, and so $x_1 + \cdots + x_m = x_{m+1} + \cdots + x_n$.
Let us now attend to the sum of $S'$. If $S$ sums to $2R$ then $S'$ sums to
$$
2n \cdot 2R + 2n = 2n(2R+1).
$$
Therefore if $n$ is even, then we are done. Otherwise, we can replace $n$ with $n+1$ throughout (equivalently, add a zero to $S$).

We now reduce the PARTITION variant to the tiling problem.
Let $S$ be an instance of PARTITION in which all numbers are odd and the sum is $2T$, where $T$ is even. Let $p$ be a prime in $(2T,3T)$. Notice that $S \cup \{p-T,p-T\}$ can be partitioned into two equal halves iff $S$ can (this is since $2(p-T)$ is larger than half the total sum, which is $[2T+2(p-T)]/2 = p$). Moreover, since $p$ is odd and $T$ is even, $p-T$ is odd.
Let $q \in (2p,3p)$ be a prime, and consider the instance $S \cup \{p-T,p-T,pq\}$. If $S$ can be partitioned into two equal halves, then we can tile a rectangle of dimensions $p \times (q+2)$ by taking a rectangle of dimensions $p \times q$ and adding two more columns corresponding to the two equal halves of $S \cup \{p-T,p-T\}$.
Conversely, suppose that $S \cup \{p-T,p-T,pq\}$ can tile some rectangle. Since $p,q$ are prime, the rectangle of area $pq$ must have dimensions $1 \times pq$ or $p \times q$ (up to switching the axes). In the former case, since all remaining numbers add up to $2p < pq$, we end up with a trivial tiling. In the latter case, since $2p < q$, the remaining numbers are not enough to fill any rows, and so we conclude that the tiled rectangle must have exactly $p$ rows. Since the remaining numbers add up to $2p$, they must tile a $p \times 2$ rectangle (or two $p \times 1$ rectangles, which is a stronger requirement). The remaining numbers are all odd, and so must correspond to rectangles with a single column. This is only possible if they can be partitioned into two equal parts.


I would say they are just personal preferences without any particular naming rules or standard attached. Just as you said, it is only a exchange of the terms. There is negligible if any other difference.
The logical choice for me is also letting Left-Right Rotation be the Left-Rotation followed by a Right-Rotation.
However, a few people might prefer to recognize Left-Right Rotation as primarily a Left-Rotation (the larger rotation) with a Right-Rotation before it (as a delta operation). In this way, both Left-Rotation and Left-Right-Rotation moves the (larger) right subtree to the left.
In case you might think this is the whole story, here is more naming confusion and conflict. People may even differ on which tree rotation should be called Left-Rotation and which one should be called Right-Rotation! Not only with AVL trees, but possibly also with other kinds of binary search trees that use rotations to maintain balance. Here is an excerpt from the wikipedia item for tree rotation.

In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape of the tree, and in particular to decrease its height by moving smaller subtrees down and larger subtrees up, resulting in improved performance of many tree operations.
There exists an inconsistency in different descriptions as to the definition of the direction of rotations. Some say that the direction of rotation reflects the direction that a node is moving upon rotation (a left child rotating into its parent's location is a right rotation) while others say that the direction of rotation reflects which subtree is rotating (a left subtree rotating into its parent's location is a left rotation, the opposite of the former). This article takes the approach of the directional movement of the rotating node.

So, should we take some action to make it more consistent? Probably not necessarily. As far as I have experienced and as far as I have checked[1][2][3][4][5], the approach taken by Wikipedia, which calls the rotation in the counterclockwise direction left rotation and which calls the left rotation followed by right rotation left-right rotation is far more popular. I will stick to that approach myself. I would recommend you stick to that approach, which you are comfortable with as well.


No. As a counterexample pick any non-trivial problem $P_2$, i.e., a problem with at least one yes instance $I_{\text{yes}}$ and at least one no instance $I_{\text{no}}$.

To reduce an instance $I_1$ of $P_1$ to an instance $I_2$ of $P_2$ first solve $I_1$ (e.g., by brute force). If the answer to $I_1$ is yes, then let $I_2 = I_{\text{yes}}$, otherwise $I_2 = I_{\text{no}}$.


There are three main approaches (that I'm aware of) for implementing higher-order functions.  Defunctionalization, closure conversion/lambda lifting, and combinators.

Let's write $A \Rightarrow B$ for the type of a higher-order function from $A$ to $B$ and $A \to B$ for the type of C-style function pointers from $A$ to $B$.  (If we wanted to formalize this, we could say that function pointer abstraction is only allowed in the empty environment.)

Closure conversion is the idea that we choose the representation $$A \Rightarrow B \equiv \exists E.(E, (E, A) \to B)$$ The $E$ will typically be the tuple holding the values of free variables at the site of lambda abstraction.  It could be some other representation though.

Lambda lifting takes a somewhat different and more global approach where a lambda abstraction is pulled outward into containing scopes adding free variables as parameters along the way, until it reaches the top-level scope.  While this deals with block structuring, to actually handle higher-order uses of functions requires allowing partial application.  You can then pass around partially applied functions, but this is basically the same representation as closure conversion.

If you wanted to eliminate function pointers we can use defunctionalization, which, in this special case, simply produces an enumeration.  There's little reason to do this though, as function pointers are natural constructs in most assembly languages.

The next approach is to use combinators.  This is basically the same as lambda lifting and using partial applications except a fixed set of top-level functions are used, and all other functions are expressed as combinations of those.  (If they don't have a predefined fixed set of combinators, then this is usually just a lambda lifting based approach like I described above.)  A higher-order function would then be effectively represented by a value in a data type using Haskell syntax like the following (using SK combinators):

data CA = S | K | App CA CA -- plus other things in reality, like primitive values

A representation more like the spine calculus probably makes more sense for efficiency.  Or you could do something like:

data CA = S0 | S1 CA | S2 CA CA | K0 | K1 CA

Applying a higher-order function splits into two cases: either a combinator has been fully applied and thus it should be executed, or we return a new value that represents the (partial) application.

I haven't done an exhaustive survey, but I'm pretty confident variations on closure conversion are by far the most common implementation strategy for higher-order functions (hence them often being called "closures").  It has the nice properties of being modular, simple, and reasonably efficient even in its naivest form.  It takes a good choice of base combinators and some cleverness to get combinator-based approaches to perform well.  Defunctionalization just isn't widely used as far as I can tell, but there is little reason not to take advantage of function pointers.  To the extent that you do, e.g. instead of a large case analysis you have a table of function pointers that you index into, you've basically recreated closure conversion.

There are some other approaches.  One is template instantiation which is basically to take $\beta$-reduction literally, and simply literally substitute terms into other terms.  Usually, this requires having and manipulating an abstract syntax tree-like structure.  Higher-order functions are then represented by their (syntactic) lambda terms or "templates" thereof which can simplify performing the substitutions.


Counting number of permutations respecting partial order

Brightwell and Winkler proved that this program is #P-complete in their paper Counting linear extensions. You can, however, estimate the number of linear extensions efficiently.


What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Hint: Reduce to bipartite vertex cover, which can be solved efficiently.


Algorithmic type checking for Calculus of Inductive Constructions

The problem of giving an algorithmic reading to the typing rules in CIC, and dependent type systems in general, is quite subtle.

One recommendation is Randy Pollack's Typechecking in Pure Type Systems, Gille Barthe's Type Checking *Injective Pure Type Systems and McKinna and Pollack's Pure Type Systems formalized.

The first basic idea is to "push" the conversion rule
$$ \frac{\Gamma \vdash t: A\quad A\simeq B}{\Gamma\vdash t : B}$$

into the application rule
$$ \frac{\Gamma \vdash t:A\quad \Gamma\vdash u:A' \quad A\simeq \Pi x: A'.B}{\Gamma\vdash t\ u:B\{x\mapsto u\}}$$

And similarly for "application-like" rules. The theorem is that these modified rules suffice for type-checking (without conversion), with the exception of a possible single application of conversion at the end.

This makes the rules type-directed, which allows a straightforward implementation. There are additional shortcuts which allow skipping verification of $\mathrm{WF}$, for example, if it is known that it is going to be derived later, or it is admissible.

As Luke notes, there is no complete treatment of such shortcuts, and the validity of these is sometimes quite complicated to prove (e.g. the "expansion postponement" rule).

Checking conversion of terms with $\delta$-reductions (defined functions) is a whole bag of worms: when checking

$$ f\ t_1\ldots t_n\simeq f\ u_1\ldots u_n$$

should you just check $t_i\simeq u_i$ for each $i$, or unfold $f$? The answer is, unsurprisingly, it depends. In general clever heuristics are used, e.g. "unfold $f$ if it is a projection, otherwise try checking equivalence of the arguments, and unfold $f$ if that fails".


Negative weight cycle vs maximum weight cycle

I don't think it's very surprising that finding a single negative-weight cycle is easier than finding the highest-weight cycle. If you ask me to find a negative-weight cycle, I can find any one and, if I give you what I claim is an answer, it's very easy for you to check the sequence of vertices and see that the weight really is negative. But the maximum-weight cycle feels like a very special object. Even if I claimed to have found it how would I convince you that there isn't another cycle with even higher weight?

On the other hand, maybe this intuition isn't helpful, since it's also trivial to check that a given cycle has weight at least 1 or 2 or 17...


If you have managed to solve $0^n1^n$ then $q_4$ should simply proceed to the rightmost bit you haven't processed yet and verify that it's a 1 and that there is nothing following it.


Why is the step property in a balancing network defined as it is?

The formula is wrong. The correct formula is
$$
y_i = \lfloor \frac{n}{w} \rfloor + [i < (n \mod{w})],
$$
where $[C]$ equals 1 if $C$ holds, and 0 otherwise.

Sometimes books contain mistakes. When you see a mistake, correct it and proceed. No need to ask us for permission.


Big-O Time Complexity of nested for loops

Hint: What is the value of sum at the end of the code, as a function of $n$? If it is $s$ then the fifth line must have been run exactly $s$ times.


Probability of reaching a state in asymmetric random walk

Suppose that $S_T > C\ln T$. Let $T_0-1$ be the last time that the random walk reached the origin. Thus if we run an unconstrained biased random walk starting at position $1$ at time $T_0$, we reach beyond $C\ln T$ at time $T$. This can only happen if $T-T_0 \geq C\ln T$.
The probability that an unconstrained biased random walk starting at position $x$ ends up to the right of $x$ after $L$ steps is exponentially small in $L$, by Hoeffding's inequality. In your case, $L \geq C\ln T$, and so this probability is polynomially small in $T$. Taking a union bound over all possible values of $T_0$ (at most $T$ of them), you can choose $C$ so that the error probability is at most $\frac{1}{T^d}$ for $d$ of your choice.
(More formally, choose the $\pm 1$ steps $\xi_1,\ldots\xi_T$ of your walk ahead of time. You start at some fixed $S_0$, which here is implicitly assumed to be $S_0 = 1$, and then $S_{n+1} = |S_n + \xi_{n+1}|$. If $S_T > C\ln T$ then $S_{T_0} + \xi_{T_0+1} + \cdots + \xi_T \geq C\ln T$, by definition of $T_0$. We bound the probability that this happens for fixed $T_0$ and take a union bound.)

As for $\mathbb{E}(S_T)$, since you have a stationary distribution, then your chain is positive recurrent (see Chapter 21 of Markov Chains and Mixing Times). Your chain is not ergodic due to a parity issue, so let's consider the square of your chain (moving two steps at once). The square decomposes into two separate chains. The one of the even integers looks as follows:

At $0$, stay at $0$ with probability $p$, and transition to $2$ with probability $1-p$.
At $2n>0$, transition to $2(n-1)$ with probability $p^2$, stay at $2n$ with probability $2p(1-p)$, and transition to $2(n+1)$ with probability $(1-p)^2$.

The one on the odd integers looks as follows:

At $1$, stay at $1$ with probability $p(2-p)$, and transition to $3$ with probability $(1-p)^2$.
At $2n+1$, transition to $2(n-1)+1$ with probability $p^2$, stay at $2n+1$ with probability $2p(1-p)$, and transition to $2(n+1)+1$ with probability $(1-p)^2$.

Let's focus on the case of even integers. Let $f_{2n} = cn$. Using $p(i,j)$ for the probability to transition from $i$ to $j$,
\begin{align}
&p(0,0) e^{f_0 - f_0} + p(0,2) e^{f_2 - f_0} = p + (1-p) e^{-c}, \\
&p(2n,2n-2) e^{f_{2n-2} - f_{2n}} + p(2n,2n) e^{f_{2n} - f_{2n}} + p(2n,2n+2) e^{f_{2n+2} - f_{2n}} = p^2 e^{-c} + 2p(1-p) + (1-p)^2 e^c.
\end{align}
For any $c > 1$, the first line is strictly less than 1. For $c = 1+\epsilon$, the second line is
$$
p^2 (1 - \epsilon) + 2p(1-p) + (1-p)^2 (1 + \epsilon) + O(\epsilon^2),
$$
which is less than 1 for any small $\epsilon>0$ since $p^2 > (1-p)^2$.
We have thus verified Popov's conditions for geometric ergodicity (see for example Isaacson), and we conclude1 that there exists $\beta < 1$ such that
$$
 \left|\Pr[S_{2T} = 2n \mid S_0 = 0] - \pi^e_{2n}\right| = O(e^{f_0-f_{2n}}\beta^T) = O(\beta^T),
$$
where $\pi^e$ is the stationary distribution of the even component of the squared chain, given by $\pi^e_{2n} = 2\pi_{2n}$. Denoting the corresponding expectation by $E^e = \mathbb{E}(\pi^e)$, we conclude that
$$
 |\mathbb{E}(S_{2T} \mid S_0 = 0) - E^e| = O(\beta^T).
$$
Similarly,
$$
 |\mathbb{E}(S_{2T+1} \mid S_0 = 0) - E^o| = O(\beta^T).
$$
We obtain similar results for any other fixed starting point.
1This equation appears in Popov's paper but not in Isaacson's.


Existence of interval arrangement satisfying constraints

Construct a graph in which each vertex corresponds to an endpoint of an interval. Then add the following edges:

If $\ell_i,r_i$ are the endpoints of $I_i$, then add the edge $\ell_i \to r_i$.
For a constraint $I_i < I_j$, add the edge $r_i \to \ell_j$.
For a constraint $I_i \cap I_j \neq \emptyset$, add the edges $\ell_i \to r_j$ and $\ell_j \to r_i$.

Now check that there are no directed cycles. (This answer is inspired by an answer on stackexchange.)


It's unclear exactly what level you're asking the question at.

In principle, you could set up a graph where the vertices are prisoners, there's an edge between any two prisoners who need to be kept separate, and each prison corresponds to a colour. In practice, there are probably too many prisoners in any reasonably sized country for this to be a computationally tractable approach (though the conflict graph would probably be rather sparse), there are more constraints on the system that would be hard to model in this graph-colouring approach, and two prisoners getting into a fight could cause a re-colouring that might cause a large proportion of the prison population to be moved, which is neither feasible nor desirable.


Showing that Hadamard is its own inverse

Rewrite your final expression as
$$
\sum_{z \in \{0,1\}^n} \left| z \right\rangle \cdot \frac{1}{2^n} \sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)}.
$$
So to complete the proof, we need to show that
$$
\sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)} = \begin{cases} 2^n & \text{if } x=z, \\ 0 & \text{otherwise}. \end{cases}
$$
If $x=z$ then $x+z = 0$ (computing modulo 2!), and so $(-1)^{y \cdot (x+z)} = 1$ for all $y$, hence the sum equals $2^n$. If $x \neq z$ then pick some $i$ such that $x_i \neq z_i$. We can partition $y$ into the $i$th coordinate $y_i$ and all the rest $y_{-i}$. Now
$$
\sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)} =
\sum_{y_{-i} \in \{0,1\}^{n-1}} (-1)^{y_{-i} \cdot (x+z)_{-i}} \sum_{y_i \in \{0,1\}} (-1)^{y_i \cdot (x+z)_i} = 0,
$$
since $x_i+z_i = 1$ (modulo 2) and $\sum_{y_i \in \{0,1\}} (-1)^{y_i} = 1-1=0$.