Halting Problem without self-reference: why does this argument not suffice (or does it)?

I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way.  I suggest sticking with a more standard presentation, such as the one you linked.  If you want to find a way to explain it in a way that minimizes the technical content, the presentation in this video is surprisingly accessible, and remains true to the logic of the standard proof.

On to the difficulties with your proposal.  In your proposal, it's not trivial to write down the code for such a Q.  Think about what it means to have the line

  if H(Q,J) then loop forever

Recall that the first argument to H is a bit-string that contains the code /  algorithm / Turing machine -- it's not a pointer to the function, but a string.  Naively, this seems to mean that we include a hardcoded string that contains the source code for Q, inside the code of Q.  But that's not possible.  Suppose the code for Q takes 100 characters.  Then we need to hardcode a 100-character string constant inside the definition of Q, plus we also need some more characters for the rest of the logic -- and that adds up to more than 100 characters.  If you think about it, it's obvious that we can't have a string constant inside the code of Q that is the code of Q, because it would be too long.

Maybe you're thinking that's not what you had in mind.  Maybe you were thinking that the programming language will have some built-in API to get the code of the current function, so actually the code you were thinking of is something like:

def Q(J):
  if H(get_source_code_of_current_function(),J) then loop forever
  else halt

OK, fine.  This proves that the halting problem can't be solved for code written in any programming language that has a get_source_code_of_current_function() API.  However, my favorite programming language doesn't have such an API.  So, this proof doesn't prove anything about my favorite programming language -- perhaps the halting problem is solvable for my language, who knows?  Similarly, Turing machines don't have such an API, so this doesn't prove that the halting problem for Turing machines is undecidable.

And that's a major flaw in your proof.  And it's a flaw that is subtle and not at all evident.  I don't think it's pedagogically a good idea to present a proof that "looks valid" on the surface but is actually, once you dig into it deeper, flawed.

Now, it is possible to rescue your proposed proof.  It actually is possible to construct a function Q that works the way you said; you basically need it to be a quine.  I suppose in principle you could explain the idea of quines, then present your proof and explain how to implement a function Q using those ideas.  But that seems like a bad idea to me, from a pedagogical perspective.  Quines are mind-bending and mysterious and freaking hard to understand.  A student who doesn't understand quines won't understand your proof.  And it makes the proof of undecidability for the halting problem look a lot more mysterious than it needs to be.  So this does not seem to me like a more accessible way to understand the halting problem.


Unary function is partially n-computable

Well there are trivial two conditions you have to prove.
If $f:N\rightarrow N$ is computable in $n$ instructions, then there exists a corresponding program $P$ that computes it in $n$ instructions. $P$ could assign one new variable in every instruction, thus the program uses $\leq n$ new variables. Furthermore the program only contains $n$ instructions meaning there is one label for every instruction at max, hence the number of labels is $\leq n$. This completes the proof (that $f$ is partially n-computable)


Modelling a dependency of multiple transitions on data in one place

I do not know if there is a variant of Petri nets that captures your intent exactly -- there probably is, there are so many -- but the feature can be expressed with regular Petri nets.

Just add a transition that creates tokens in multiple places, one per original transitions. Then, all three follow-up transitions can fire after the preceding one is done.

Introduce whatever syntax you want to express this neatly, and implement it using multiple places in the backend.


Is there a formal definition of "data structure"?

No, the term doesn't have a formal definition.

You might be interested in the notion of an abstract data type, which does have a formalization.


How do we know $\neg \neg LEM$ isn't provable in MLTT?

The task here is indeed to find a model of MLTT in which $\neg LEM$ holds (and so $\neg\neg\neg LEM$ holds as well). Realizability models have this feature, for instance; see also this. Here, MLTT functions are interpreted with codes of computable recursive functions, so the usual uncomputable functions, e.g. halting oracles, cause $LEM$ to fail.

If you define $LEM$ as ranging over all types, and not just types which are propositional (i.e. have at most one inhabitant up to propositional equality), then it is also the case that $LEM$ is inconsistent with the univalence axiom of homotopy type theory, so this version of $LEM$ is also refuted by any model which can interpret the univalence axiom. Such are the simplicial set and cubical set models.

$LEM$ is also inconsistent with parametricity, so models validating parametricity also refute $LEM$. I think formally these are considerably simpler than univalent or realizability models; see for example the reflexive graph model. Intuitively, this works by noticing that MLTT does not allow inspecting the structure of types, so any function with type $\prod_{A : Type} A \rightarrow A$ must be the identity function. However, $LEM$ allows one to branch on whether two types are equal, allowing a function with the above type which is not the identity function on all types, e.g. negates Boolean inputs.


Using humans as components to build a computer?

Actually, until the 1950s the word computer was used to refer to a human who did arithmetic calculations.  One (or more) of Richard Feynman's (many) autobiographies contains anecdotes about his time on the Manhattan project, where he ran the group of human computers. For arranging a group of humans to perform a complex computation they wouldn't start with discrete logic components, but rather have each human perform multiple arithmetic operations and then coordinate their results (along with some error checking.)  How to organize these kinds of large computations may be covered in numerical methods books from the 1940s or early 1950s.

The first version of the Logic Theorist by Newell, Simon and Shaw was simulated using humans in 1956 (less expensive than computer time).  They later won a Turing Award for basic contributions to AI, the psychology of human cognition and list processing (the Logic Theorist may have been the first program to use linked-lists to represent data structures.)  And the experience influenced Simon's later ideas on emergent behavior (see his Sciences of the Artificial.)

As pointed out in the comments and other answers, there is now an emerging discipline of Human-Based Computation, where various incentives are used to get humans to do parts of a larger calculation, where those parts make good use of human problem solving or pattern recognition.  One example of this is reCaptcha, where users need to enter two words to prove that they are not a bot, one a distorted image that is used for the actual "proof" and the second an actual word from a scanned book, which is used to produce a digitized version of the book.  Another example is the Amazon Mechanical Turk where a business can outsource "microtasks" to human workers for small sums of money.  The mechanical turk has been used, for example, to collect annotations on 250,000 images for image processing research.  The key seems to be breaking the problem down into a pile of independent work items, with significant amounts of redundancy used to reduce errors.  (E.g., you assign the same work item to 2 different humans, and then if they provide conflicting answers you assign the work item to a third human to resolve the difference.)


Stan has two pure strategies for each type of card. Since there are three types of cards (H, M, L), in total he has $2\times 2\times 2 = 8$ strategies. Here is a list of them:

Always stay.
Always raise.
Stay only if H.
Stay only if M.
Stay only if L.
Raise only if H.
Raise only if M.
Raise only if L.


What is the relationship/difference between best/worse/expected case and big O/omega/theta?

Why would an algorithm have different bounds if the inputs/scenarios are the same?

A deterministic algorithm has a single running time on each input. However, this is not what best case, worst case and average case are about. Let us consider a deterministic sorting algorithm. Its running time on an array of length $n$ depends on the array (and on the algorithm).
The best case running time is the minimal running time of the algorithm on an array of length $n$. The worst case running time is the maximal running time of the algorithm on an array of length $n$. The average case running time with respect to a distribution on arrays of length $n$ is the average running time of the algorithm on an array chosen at random from the given distribution.

For a randomized algorithm, it makes sense to consider the best case, worst case and average case for a single input, but this is not what these terms usually refer to.

  "Best, worse, and expected case describe the big O for expected inputs and scenarios."

This is simply wrong. I have explained above the meaning of best case, worst case and average case running time for the particular case of sorting algorithms, and the general case is similar.

How is running time measured? One way to measure running time is via an experiment – choose an actual machine, code the algorithm in a particular way, and measure the running time. However, this approach is problematic – which machine should we run the code on? How should we implement the algorithm? Another problem that the exact formula for the running time might be very complicated, and so not very helpful.

The way out is to state the running time up to a constant factor. This makes sense since under reasonable assumptions, the exact machine used and the exact implementation only affect the running time by a constant factor. Moreover, this allows us to hide the complexities of the exact running time by sweeping them under the rug of asymptotic notation.
(As an aside, we measure the running time on an abstract machine known as the RAM machine, which has unbounded memory. This allows us to make sense of arbitrary input sizes.)

Consequently, we always quote the running time in asymptotic notation. It is common to use big O notation, but this is in fact only an upper bound on the running time. Merge sort, for example, runs in time $O(n^5)$. It also runs in time $O(n\log n)$, and this upper bound is tight, in the sense that the worst case running time is $\Theta(n\log n)$.
When quoting the running time as $O(f(n))$, what one usually means is that the worst case running time is $\Theta(f(n))$. The reason we use big O rather than big $\Theta$ is that on some inputs the algorithm may run faster, and so for arbitrary inputs it may not be correct that the running time is $\Theta(f(n))$, but it is always correct that the running time is upper-bounded by $O(f(n))$.

  "Big O, big omega, big theta describe the upper, lower and tighter bounds for the run-time."

Big O, big $\Omega$ and big $\Theta$ are general-purpose asymptotic notation. They can be used to express asymptotic estimates on the rate of growth of arbitrary functions. Even in computer science, it is common to use asymptotic notation not only to measure running time, but also to measure memory consumption; and in other fields asymptotic notation is used for functions not related to algorithms at all.


Does there exist a priority queue with $O(1)$ extracts?

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree.

It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just follow the start pointer, remove the minimum and change the pointer to the minimum's next. The minimum can never have a left child; if it has a right child, we put it in the minimum's place in the tree. We do not perform the splay operation splay trees usually would do.
The result is a search tree that is still reasonably balanced: because we only remove nodes on the left flank, we know that when the number of nodes (in an affected subtree) drops to about half the original number because of deletions, the (sub)tree's height is reduced by one.

Insertions are possible in $\mathcal{O}(\log n)$ amortised time; the zig-zag (and what not) operations will here also rebalance the tree nicely.

This is a rough sketch at best. Credits go to F. Weinberg who puzzled over the question with me and our advisor M. Nebel who mentioned splay trees, about the only tree variant we had not tried.


General version of pumping lemma for regular languages, how many partitions to consider

The general version of the Pumping Lemma specifically applies to all strings $uwv \in L$ such that the length of $w$ is greater than or equal to a certain constant (the pumping length). No matter what $u$ and $v$ you pick, so long as whatever's between them is long enough, the general version will work.

So you don't need to consider all $u$ and $v$, only the ones that are useful to solving your problem. For instance, if you have the language $0^a 1^b 2^b 3^c$ where $a$, $b$, $c$ are positive integers, you can let $u$ be the string of zeroes at the beginning, let $v$ be the string of threes at the end, and then apply the simpler version of the lemma to the remaining part.

Conversely, the choice of $x$, $y$, and $z$ is harder, because the lemma doesn't guarantee that it works for all choices of these substrings, only for at least one choice of them.


Context-sensitive grammars for $a^ib^jc^{ij}$ and $a^ib^jc^{i^j}$

Designing context-sensitive grammars (with productions $\alpha X \gamma \to \alpha \beta \gamma$ with $\beta \neq \varepsilon$) is no fun at all. It is slightly more convenient to construct monotone grammars (with productions $\alpha \to \beta$ with $|\alpha| \le |\beta|$). There is a standard construction from one to the other.

But even then it is full of tiny details that have to be observed.

It is relatively easy to construct a grammar for $\{ La^ib^jc^{ij} \mid i,j\ge 0 \}$.
First generate strings of the form $LB^jA^i$, just like in a context-free grammar. Add the rule $BA \to ABC$, so that if every $A$ moves over every $B$ we generate $ij$ $C$'s. But now we have $C$'s in between. Let $B$'s move over $C$'s whenever needed.

Then we have to rewrite $A,B,C$ into $a,b,c$ respectively provided they are in the right order. This can be done using the boundary symbol $L$ and the productions $LA \to La$, $aA \to aa$, $aB\to ab$ etcetera. Like a finite state automaton that accepts $a^*b^*c^*$.

Now what about the $L$? We used it to mark the start of the string. According to the rules of monotone grammars it cannot be deleted. Well, let the $L$ double as one of the $a$'s. But then we should carefully match the $c$;s with the new design. Thus start by generating the context-free language  $aB^jA^iC^j$.

Done? not yet. We now always have at least one $a$, i.e., $i>0$.   Add these special cases.

Problem with the construction is its correctness. Productions can be applied in any order, not only the one order you have considered during its construction.


What is the complexity of determining whether or not conjunction of positive CNF and negative CNF is satisfiable?

Given a CNF, which is a conjunction of positive CNF and negative CNF, what is the complexity of the problem to determine that this special case of CNF is satisfiable?

The problem is provably NP-complete by reduction from CNF satisfiability.

Each negative literal $\lnot{x}$ in a CNF SAT instance can be converted to a positive literal by replacing all occurrences of it with a new variable $z$ plus the following two CNF clauses: $x \lor z$ and $\lnot{x} \lor \lnot{z}$.  The clauses force $z$ to act as the same constraint as $\lnot{x}$.  Once all the original negated literals have been replaced, you are left with clauses that contain either all positive or all negative literals.  Since any CNF SAT instance can be reduced to this form and since CNF SAT is NP-complete and since your problem is trivially in NP, your problem must be NP-complete.


What is the difference between LRU implemented for a cache and for page replacement?

LRU is most commonly used in 2-way associative caches, where it only requires a single bit that is set or cleared depending on the way accessed. (True LRU requires log2(N!) bits for N ways for each set.)

For four-way and eight-way associativity, binary tree pseudo-LRU is commonly used, though some embedded systems might implement true LRU as such is easier to analyze for worst-case execution time. Binary tree pLRU is relatively simple to implement because an access to a given way will always merely set/clear specific bits.

For associativities higher than eight, FIFO, random, and Not Recently Used have been used. E.g., the Itanium 2 6M used NRU that is similar to the clock page replacement algorithm in that a bit is set when accessed and all the bits are cleared when they have all been set.

An interesting exception is the use of true LRU in the 32-entry fully-associative L1 TLBs for several Itanium implementations. For a fully associative TLB, true LRU is less expensive because there is only one set, so storage and control logic can be bundled together.

It should also be remembered that LRU is really just an estimate of relative reuse distance; approximation of a conceptually-derived heuristic can be roughly as effective as the ideal heuristic. (Even reuse distance may not be ideal for replacement because not all entries have the same cost/benefit.)


Augment the string "abcde" with # as start and end markers to get #abcde#. Now, as @Yuval Filmus pointed out,  we need to make some assumption about the kind of model that generates this data. Because we have both unigram and bigram counts, we can assume a bigram model. In a bigram (character) model, we find the probability of a word by multiplying conditional probabilities of successive pairs of characters, so:

$\Pr[\#abcde\#] = \Pr(a|\#)*\Pr(b|a)*\Pr(c|b)*\Pr(d|c)*\Pr(e|d)*\Pr(\#|e) $

To find the conditional probability of a character $c_2$ given its preceding character $c_1$, $\Pr(c_2|c_1)$, we divide the number of occurrences of the bigram $c_1c_2$ by the number of occurrences of the unigram $c_1$.

So, for example $\Pr(e|d) = count(de)/count(d) = 64/150$


What is the optimal solution of the 1962 Procter and Gamble's TSP Contest?

Full details are in Robert L. Karg and James L. Thompson, A Heuristic Approach to Solving Traveling Salesman Problems (Management Science, 10(2):225–248, 1964).  The PDF is available from JStor and Informs.org (both paywalled). This is the paper that produced the optimal tour of 10,861 miles. It also includes the full distance table but I'll not reproduce that here as it's way too much typing.

The solution is also illustrated on page 15 of The Traveling Salesman Problem by David L. Applegate, Robert E. Bixby, Vasek Chvátal and William J. Cook (Princeton University Press, 2007). The introduction to that book, which includes the relevant page, is freely available from the publisher.


What are some of the practical applications of CSP process algebra?

CSP is the formal basis of the programming language Occam which compiled to INMOS Transputers. Transputers appeared in all sorts of devices, such as set-top boxes for satellite TV. Eventually, however, the company doing all of this work failed to achieve commercial success, and was eventually absorbed by another company.


AVL Tree - Print ascending using in-order

AVL trees, like all other binary search trees, have the following guarantee:

  Suppose that $v$ is a node with left child $l$ and right child $r$. If $x$ is a node in the subtree rooted at $l$ and $y$ is a node in the subtree rooted at $r$ then $key(x) \leq key(v) \leq key(y)$.

Using this, you can easily prove by induction that the inorder traversal of a binary search three produces a list of keys in nondecreasing order.


What data-structure is best suited for escape analysis?

Escape analysis is a static analysis that determines whether the
lifetime of data exceeds its static scope. As such, it is not really
about stack vs heap allocation, just about lifetimes.

I don't think you can use your typed AST for escape analysis, because
what you are analyzing is the data flow of the program. The
appropriate structure for that is a graph, not a tree, because the
data flow is cyclic. So what you want is to build a control flow graph
(cfg), and perform data flow analysis on it.

Data flow analysis is a method or family of methods used for
implementing a whole range of compiler optimizations. Among them,
escape analysis. In it, you keep track of all objects, variables and
references of your program in a points-to graph. Each object and
variable is a node in the graph and, depending on how you implement
it, references between them can either be nodes or edges.

For example, consider this Java method:

public Pair myMethod(Pair[] pairs) {
    Foo f = new Foo();
    Pair p1 = new Pair(1, 2);
    Pair p2 = new Pair(3, 4);
    p1.value = f;
    pairs[0] = p1;
    return new Pair(5, 6);
}

Escape analysis would work roughly like this:

Line 1: An array of type Pair is passed into the method and a
Pair is returned from it. Add two nodes to the graph, one labelled
pairs and another labelled RETURN both with flagged foreigner.
Line 2: An object called f is created in the myMethod
method- Add a node labelled f with flag native to the graph.
Line 3-4: Add two more native nodes labelled p1 and p2.
Line 5: The field value of p1 is set to refer to f. Add an
edge from node p1 to f.
Line 6: First element of the pairs array is set to refer to
p1. Add an edge from pairs to p1.
Line 7: A new pair object is returned. Add an anonymous native
node representing the pair object to the graph. Then add an edge
from the RETURN node to this anonymous node.

After this step, traverse the graph beginning at the foreigner nodes
and flag all nodes visited as foreigner. It is exactly the same task
as the mark step in a mark and sweep garbage collector.

Then all objects that weren't reached by the traversal retain their
native flag and are eligible for stack allocation provided that the
compiler can statically determine their sizes. The rest must be
allocated on the heap.

I highly recommend watching the Youtube lectures of this professor:

https://www.youtube.com/watch?v=NVBQSR_HdL0
https://www.youtube.com/watch?v=LfAYWms9gUc

The
paper
Escape analysis for Java
also provides a fairly good description on how the algorithm works.


Minimize longest continuous streak of $1$s after flipping $m$ $-1$s to $1$s

You can use dynamic programming. It is very likely that much faster algorithms exist.

Given a string $w$ of length $n$, for $0 \leq i,j \leq n$ and $0 \leq k \leq m$ you compute the minimal maximum 1-run in $w_1,\ldots,w_i$ given that $k$ many -1s were changed to 1s, and given that $w_1,\ldots,w_i$ ends in a 1-run of length $j$.

This gives an $O(n^2m) = O(n^3)$ algorithm.


Algorithm for identifying polygons (set of points)

I'll assume you are given two sets of points and want to determine whether one can be transformed to match the other.   This is the pointset registration problem in computer vision.  There are standard algorithms for this problem.

One of the crucial challenges is outliers -- e.g., points in the first set that don't have any corresponding point in the second set, or that have a large amount of error in their location.  If you don't have outliers in your setting, then the problem becomes noticeably easier: simple least-squares linear regression might suffice.

If you have to deal with outliers, one standard way is to use RANSAC to find a rigid transformation that, when applied to the first set, makes it match the second set.  A rigid transformation is determined by the correspondence between two points.  So, you can use RANSAC: repeatedly pick a pair of points in the first set, choose a candidate pair of points in the second set for them to be matched to, compute the rigid transformation that maps the first two points to the latter two points, apply it to all points in the first set, find all inliers (points that are well-matched), update your estimate of the rigid transformation, count the number of inliers, and do this many times and keep the best rigid transformation you've found.

There are many other approaches as well.  If you do some research, you should be able to find many algorithms, techniques, and even existing tools.


How to do last step of Krom's algorithm for solving 2SAT problems

The first step in implementing an algorithm is understanding why it works.

In your case, Krom's algorithm is based on repeated application of the resolution rule
$$
\begin{array}{c}
a \lor b \qquad \bar{a} \lor c \\\hline
b \lor c
\end{array}
$$
Here $a,b,c$ are literals. This rule is valid, and applied to two 2-clauses produces a 2-clause. Hence there is no harm in running it until reaching a point at which it can be applied no more. If in this way we reach a clause $a \lor a$, then the literal $a$ must be true. So if we reach both $a \lor a$ and $\bar{a} \lor \bar{a}$, there is no solution.

More interestingly, if all solutions have $a$ set to true, then the completeness of resolution implies that $a \lor a$ will be generated.

This suggests the following algorithm:

Generate all 2-clauses reachable by resolution.
If you have generated both $a \lor a$ and $\bar{a} \lor \bar{a}$ for some variable $a$, then there is no solution.
Otherwise, if for some variable $a$ we have generated neither $a \lor a$ nor $\bar{a} \lor \bar{a}$, add one of them as you please and go back to step 1.
Output the truth assignment satisfying all literals $a$ for which we have generated $a \lor a$.

This is just one implementation; others are possible. (For example, we could immediately substitute any known values before step 3.)

Back to your example: $a \lor b$. Step 1 produces no new clauses. The variable $a$ is "free", so in step 3 we add (say) $\bar{a} \lor \bar{a}$. Step 1 is now more interesting:
$$
\begin{array}{c}
a \lor b \qquad \bar{a} \lor \bar{a} \\\hline
b \lor \bar{a}
\end{array}
\\
\begin{array}{c}
a \lor b \qquad b \lor \bar{a} \\\hline
b \lor b
\end{array}
$$
We can now read off the truth assignment $a=F,b=T$.

Had we added $a \lor a$ instead, step 1 would still not do anything, and so we would add either $b \lor b$ or $\bar{b} \lor \bar{b}$ in step 3, and then read off one of the truth assignment $a=T,b=T$, $a=T,b=F$.


Finding an algorithm that minimizes vertex weight sum of a subgraph that satisfies several constraints

Without loss of generality we can assume the graph is connected.  (If not, decompose it into connected components, and solve the problem separately on each component.)  Since it is connected, every vertex has a path to every other, so we can ignore the requirement to have a path to a root.
So your problem becomes: given $R$, find a minimum dominating set $V'$ that contains $R$.  This is NP-complete; indeed, the special case where $R=\emptyset$ is the standard dominating set problem, which is NP-complete, so your problem is, too.
If you need to solve your problem in practice, you could apply any of the standard techniques for dominating set or set cover.  For instance, you could use an approximation algorithm or greedy heuristic to get an approximate solution; or you could use a SAT solver or ILP solver to get an exact solution and hope that it terminates in a reasonable amount of time on your specific problem instances.


The most conspicuous use of big O notation is in the analysis of running times of algorithms. Since the exact running time depends on the cost of specific instructions, there is no point in saying that a certain algorithm takes time $14.3n$. Also, it is difficult, and pointless, to analyze everything exactly. Big O notation hides all these details while keeping the nucleus, which is the asymptotics of the running time. As an example, since quicksort is $O(n\log n)$ while insertion sort is $O(n^2)$, you should expect the former to outperform the latter for large values of $n$. (Of course, it all depends in practice on the so-called hidden constants.)


Expressing that a function converges to 1 with linear rate using Landau notation

Both of the options you listed are acceptable. They have the same meaning; $f\in O(1/n)$ if and only if $1/f \in \Omega(n)$.

Let $f\in O(1/n)$. Then there exist $n_0,M>0$ such that for all $n>n_0$, $f\leq M/n$. Then $1/f\geq n/M$ for all $n>n_0$, thus $1/f\in \Omega(n)$, since for $n>n_0$, $1/f \geq 1/M \cdot n$.

The other direction is similar.


How to identify when to use Genetic Algorithm/Programming

The key point in deciding whether or not to use genetic algorithms for a
  particular problem centers around the question:

  what is the space to be searched?

  If that space is well-understood and contains structure that can be exploited by special-purpose search techniques, the use of genetic algorithms
  is generally computationally less efficient. If the space to be searched is
  not so well understood and relatively unstructured, and if an effective GA
  representation of that space can be developed, then GAs provide a surprisingly powerful search heuristic for large, complex spaces.

(De Jong, Machine Learning, 1990 nr 5, pg. 351)

Here a key point is what is an effective GA representation.

GA initially detects biases in low-order schemas and converges on this part of the search space. Over time, biases in higher-order schemas are detected by combining information from low-order schemas (via crossover) and eventually GA converges (at least according to the building blocks hypothesis).

Situations in which lower-order schemas give misleading information to the GA
about the probable fitness of higher-order schemas are said deceptive.

Most efforts at characterizing the difficulty of problems for GA
have concentrated on deception, but there are other factors:

the presence of multiple conflicting solutions or partial solutions
the amount of information from lower-order building blocks (not
how much this information is misleading)
sampling error
the number of local optima in the landscape
...

A general relation between a given problem's structure and the expected GA
performance on that problem is a very open area of research (actually it's not even clear what is the relation between the degree of deception in a problem and the problem's difficulty for the GA).

In general GA is more suited to find good solutions quickly than to finding the absolute best solution to a problem.

Some references you could find interesting are:

What Makes a Problem Hard for a Genetic Algorithm? Some Anomalous Results and Their Explanation by Stephanie Forrest and Melanie Mitchel (Machine Learning 1993)
Fitness distance correlation as a Measure of Problem Difficulty for Genetic Algorithms by Terry Jones and Stephanie Forrest
Dealings with Problem Hardness in Genetic Algorithms by Stjepan Picek and Marin Golub (2009)


Yes, this is possible.  It is called steganography and there are many techniques that can be used -- there is an entire literature on the subject.  You might enjoy reading about it.

It still won't stop traffic analysis.


What is the relation between universality and chaotic behavior in Elementary Cellular Automata?

Chaotic behavior does not seem to imply universality, from what I can see.  I don't see any reason to expect it would.

For instance, here's an example to challenge your intuition that the two concepts are somehow related.  Wikipedia lists the dynamic system given by the map $x \mapsto 4x (1-x)$ and $y \mapsto x + y \bmod 1$ as an example of a chaotic system.  However I doubt that this system is universal in any meaningful sense.

As David Richerby wrote, the way you prove universality is "by proving that the thing can simulate some other universal system".  I don't think "chaotic behavior" -- whatever that might mean -- is a helpful guide to determining whether a particular system is universal.


What can't guarded fragment of FO express?

You're correct that, if the structure you're working with has a universal relation, then using that relation as a guard is equivalent to having no guard at all. However, you don't get to pick the interpretation of the relation symbols. For example, if you're trying to write a formula that is satisfied by exactly the class of 3-colourable graphs, then you should think in terms of an adversary supplying you with an arbitrary graph and your formula has to give the right answer, without being able to rely on any particular properties of the structure you're given.


How does data travel in a butterfly network?

The description you were given is indeed phrased in a confusing way.  I suspect they're talking about messages travelling from top to bottom.

I suspect by "output switch" they might mean "output from the processor" (input to the butterfly network), which is pretty confusing.  That explanation could have been phrased better.

Butterfly networks are described in many places.  You might want to find another description of butterfly networks and read that.


Consider a social network. The goal is to find in the in the network a largest group of people who are all friends with each other.

This is the Maximum Clique problem, one of the canonical NP-complete problems. On general graphs it probably cannot be solved efficiently, though social networks, with their very particular structures, may lend themselves to more efficient solutions.


Removing left factoring from Context-Free Grammar

Your grammar can be abbreviated as follows:
$S \rightarrow  a^{m}b^{2m}c^{n+2}d^{n}\;|\;(a^{*}(ba|b)|bb)S\;|\;bScS; \; m,n \ge 1$
You can't factor out, for instance, the subexpressions generating the sequences of $a$'s that appear on the left. The language is not even LL($k$), let alone LL($1$).
Consider the following analogous, and simpler, example:
$S \rightarrow aS\;|\;T\; \\
T \rightarrow aTb\;|\;\varepsilon$


Is the language $L = \{a^nb^m : n = 2^m\}$ context-free?

You have stated that pumping $s$ $i$ times will give a string which contains $2^p+(i-1)*j$ $a$'s and $p+(i-1)*k$ $b$'s where $1 \le j+k \le p$. For the given language $L$ to be a CFG, new string must also belong to $L$ for all valid values of $i$.

Put $i=2$. This gives a string containing $2^p+j$ $a$'s and $p+k$ $b$'s. For this to be of the form $a^{2^m}b^m$, we need $$2^{p+k} = 2^p+j$$ This implies $$j = 2^p*(2^k-1)$$

Case 1: If $k = 0$, then from the above equation, $j$ must be $0$. But, this implies, $|vy| = 0$. So, this case is not possible

Case 2: If $k \ne 0 $, then $j \ge 2^p \ge p$, but this is also not possible since $|vy| \le p$. So, the equation  $$j = 2^p*(2^k-1)$$ is not possible.

Therefore, we cannot split the string $s = a^{2^p}b^p$ satisfying all constraints. So, the language $L$ is not Context Free.


Maybe.

Consider the problem of calculating $a^{a^b} \bmod p$. What we do here is calculate $x = a^b \bmod (p-1)$, which is the exponent we need to do $a^x \bmod p$, which is our answer. This is due to Fermat's Little Theorem, which states that for prime $p$:

$a^{p-1} \equiv 1 \bmod p$

You may notice that this intermediate exponential is smaller. Also, given a composite modulus, we can break it into factors, calculate for each of the those factors separately and combine with the Chinese Remainder Theorem. So the modulus can shrink pretty fast.

This means that a power tower can only grow to a certain size, beyond which the modulus used to calculate the upper parts of the tower is zero, so the part of the tower above that threshold has no effect on the result.

So tetration at least may be easier than it would at first appear. That said, there is also the requirement that you can swiftly factorize p, which makes large p difficult to work with.


What is the difference between designing an algorithm that solves a problem and creating a TM that decides a language?

Depending on the problem, there might not be any difference.
If the problem's goal is to answer a yes/no question, then there is no difference; accepting the input is equivalent to answering yes, and rejecting is equivalent to answering no.
However, if the goal of your problem is to output something else (e.g., output a number), then it is not identical to deciding a language.  There are still ways to formulate a corresponding language, but the correspondence is not quite as direct.
To learn more, see https://en.wikipedia.org/wiki/Decision_problem, https://en.wikipedia.org/wiki/Function_problem, https://en.wikipedia.org/wiki/Optimization_problem, https://en.wikipedia.org/wiki/Formal_language.


What linked list data structure adjustments would give me fast random lookup?

One simple approach might be to use a doubly-linked list of extents, where each extent represents a sequence of contiguous records.  The records within each extent could in turn be represented with a doubly linked list.

This preserves your ability to do $O(1)$ time splicing, and now the insert operation takes $O(k)$ time, where $k$ is the number of extents (rather than $O(n)$, where $n$ is the number of records).  If you have many fewer extents than records, this might be a partial improvement.

I don't know whether this will be better than a simple skip list or binary tree.

Note that if you use a binary tree, you can still do efficient splicing.  The splicing operation is no longer $O(1)$ time, but it can be done in $O(\log \ell)$ time, where $\ell$ is the number of records in the spliced segment.  This is not as fast as $O(1)$ time splicing, but depending upon the relative frequency of your different operations, it is another data structure you could consider (e.g., benchmark on realistic data sets).

And, of course, you could combine these ideas, e.g., with a binary tree of extents, where each extent is in turn a doubly-linked list of contiguous records.  Inserts will take $O(\lg k)$ time, and splicing can be done in $O(\lg \ell)$ time (both of which might potentially be better than the $O(\lg n)$ achieved through a simple binary tree).


Generative Machine Learning algorithms on tree structure

It sounds like what you want is a machine learning algorithm that works on trees, in the supervised learning context.  I'd imagine there are probably many machine learning algorithms that could be adapted to this setting, but a natural one to try first is naive Bayes.  So, let me sketch how to use naive Bayes in this setting.

First, we need a feature set.  A simple feature set would be: each possible subtree that appears anywhere in the training set is a feature.  So, in the example in the question, your feature set would include the subtree (NP (JJ new) (NN year)) and (JJ new) and every subtree of every parse tree that appears in the training set.  Let $S_1,\dots,S_n$ denote these $n$ subtrees.  This gives you a bunch of features.  Now you can label each sentence with its label (positive or negative); and for each, you know whether it contains that feature or not.

Now remember how Naive bayes works.  We have a boolean random variable $Y$ that indicates the class of an item, and $n$ boolean random variables $X_1,\dots,X_n$ that indicate which features it has.  In particular, $X_i=+$ means that the $i$th feature is positive, i.e., that the $i$th subtree $S_i$ is a subtree of the current item.  We want to calculate

$$\Pr[Y=+ | X_1=x_1,\dots,X_n=x_n].$$

We do this using Bayes theorem.  In particular, we use our training set to calculate

$$\Pr[X_i=x_i | Y=y],$$

for each of the 4 possibilities of $x_i,y$.  Then, we use Bayes theorem to compute $\Pr[Y=+ | X_1=x_1,\dots,X_n=x_n]$.

Now everything works as usual for naive Bayes.  We've converted this into a situation where there's a set of $n$ features that can be present or absent for each item, and we want to label all the items; there's no more need to reason about the tree structure, we can just use a standard classifier like naive Bayes.  You could also plug in some other classifier as well, too; hopefully you can see how this might work, from here.


What's the input to the decoder in a sequence to sequence autoencoder?

I was wondering the same and just stumbled across a nice tutorial by Quoc V. Le. The following explanation deals with the conditional case since this seems to be the common case. My explanation is based on and the image is taken from chapter 5 Sequence output prediction with Recurrent Neural Networks.

Background

We only regard a decoder with a single cell RNN which has:

W input to hidden weights
U hidden to hidden weights (ignore that first weight is different here)
V hidden to label weight

$$
f(x) = Vh_T \\
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ h_t = \sigma ( U h_{t-1} + W x_t ) ~~~ \text{for} ~ t = T, \dots, 1 \\
~~~~~~~~~~ h_0 = \sigma ( W x_0 )
$$

Since we are doing sequence prediction, we are not only interested in the last output of the RNN but rather the output at every timestep. Therefore the conditional decoder is designed to predict each label based on the previous ones, mathematically it splits the conditional probability in the following way:

$$
p(y|x) = \prod_{i=1}^n p(y_{i} | y_{i-1}, \dots, y_{1}, x)
$$

Like often done in machine learning, you can transform the probability to a score/energy/whatever which consists of a more convenient summation:

$$
\log p(y|x) = \sum_{i=1}^n \log p(y_{i} | y_{i-1}, \dots, y_{1}, x)
$$

The maximization of that score over our data is the objective. That can be equivalently formulated by the minimization of $ - \sum_{(x,y) \in D} \log p(y|x) $ where $D$ is our training set.

To complete this thought: When this probability is approximated we are actually interested in the argument $\theta_{min}$ of the minimization of $ - \sum_{(x,y) \in D} \log f(y|x,\theta) $ where $f(y|x,\theta)$ is our function approximator, e.g. a RNN, and $\theta$ the vector containing all weights $U$, $W$ and $V$.

During Training

During training we have the ground truth at hand so we can feed the decoder (see image) with the respective previous label at each timestep. At the first timestep we use the output of the encoder. Easy peasy.

During Inference

Here we obviously do not have the ground truth so instead we use the output of the previous timestep. This however poses another problem, since to find the sequence of maximum probability, we would have to compute every possible sequence and its probability according to probability function defined above.

Now, apparently one "greedy" approach is, to just ignore the above probability model and take the argmax's of each timestep.

Another more faithful approach is Beam Search which just heuristically looks at a subset of probable sequences and picks the one with maximum probability of them.

Things to note:

Inference is stopped, when the End-Of-Sequence symbol (<EOS>) is returned (greedy: when a timestep's argmax is <EOS>, beam search: the currently regarded sequence leads to <EOS>)
Both inference methods do not gurantee retrieving the sequence with maximum probability
The output of $f(x,\theta)$ needs to be a probability distribution at each timestep, so the final activation of the RNN is usually a softmax $f(x) = softmax(Vh_T)$

Unconditioned Case

I'd say based on the above explanation and the paper you referenced, that the unconditioned case does only get input at the first timestep of the decoder and then just "works with" the propagation of the hidden states. So the second equation of the RNN equations changes to $h_t = \sigma ( U h_{t-1} )$.

Then the outputs at each step would not be conditioned on the previous timestep's output, but rather be unconditioned. This way the modelled probability would become

$$
p(y|x) = \prod_{i=1}^n p(y_{i} | x)
$$

and the greedy inference strategy would become valid.


It's not necessary to compare to an intermediate algorithm, just to the best possible.

For example, consider the following terrible algorithm for approximating the distance between two vertices in a graph: if the vertices are adjacent, return $1$; otherwise, return $n$, the number of vertices.  This gives an $n/2$ approximation: in the worse case, the true distance is $2$ but the algorithm returns $n$.

But perhaps you're concerned that we might not know the true optimal value – after all, it's probably hard to analyze and compute. That's why we're using an approximation algorithm, right? So let's imagine that the distance between vertices is really difficult to calculate so we don't actually know what the worst case of our approximation algorithm is. At that point, you can start using approximations or, rather, bounds on the optimal value. So, for example, somebody might say, "Hey, I've no idea what the greatest possible distance between two vertices in a graph is but I know it's the length of the shortest path. A path has to use some set of edges, and use them once each. I know there can't be more than $n^2$ different edges in a graph, so the worst-case distance can't be more than $n^2\!$. Therefore, the approximation ratio can't be any worse than $n^2/2$." And they'd be right: the approximation ratio isn't any worse than that. The "more sophisticated" analysis in the previous paragraph gave a better bound on the approximation ratio.


Can we count the number of inversions in time $\mathcal{O}(n)$?

There are $o(n\log n)$ algorithms in the RAM model. Dietz gave an $O(n\log n/\log\log n)$ algorithm in his 1989 paper Optimal algorithms for list indexing and subset rank, and Chan and Pătraşcu gave an $O(n\sqrt{\log n})$ algorithm in their 2010 paper Counting inversions, offline orthogonal range counting, and related problems. Chan and Pătraşcu also gave an $O(n)$ algorithm for finding a $1+\epsilon$ approximation, for any $\epsilon>0$.

If you only allow comparisons, then there is an $\Omega(n\log n)$ lower bound, see this question on cstheory.


A simple way to do it is to just write an interpreter that follows the transition table. I.e., do something like (in C):

state = INITIAL;
symbol = get_next();
while(symbol != END) {
   state = table[state][symbol];
   symbol = get_next();
}
if(is_accepting(state))
   /* Accept */

Next simpler is to write a rat's nest of gotos, transferring among them according to the symbol at hand (each label in the program corresponds to a state of the automaton).

Writing a decently organized,structured program from an automaton is possible, but far from automatic (and it would take a fair amount of work to check it really is faithful to the automaton).


how to find all negative weight cycles(elementary circuit) in a strongly connected directed graph?

My current strategy is:

first enumerate all elementary cycles. I use the hawick algorithm which is already implemented in the c++ boost library.
sum all the weights of edges in each cycle and then check if the sum is negative.


Learning juntas, with membership queries

Information theory shows that you need at least $\log_2 \binom{n}{k}$ queries. When $k$ is small, this is $\Theta(k\log n)$, which is probably enough. Consider for example the case $k=1$, and suppose for simplicity that $n$ is a power of $2$. By feeding the inputs $x_i = \text{bit $r$ of $i$}$ to $f$ you can recover the index $i_1$. (To determine whether the function is $i_1$ or $\lnot i_1$, feed the all-zero vector to $f$.)


That's because memory is usually byte-addressed.  The address that you load from is an address of a byte in memory.  Each address refers a different byte in memory.  For a 32-bit address, there are $2^{32}$ different possibilities for the address, so $2^{32}$ different bytes that the address could refer to (and no overlap among these bytes).  $2^{32}$ is equal to 4GB.

If we had a hypothetical machine where memory was bit-addressible, then it would indeed be 4Gb, i.e., 4 gigabits instead of 4 gigabytes -- but no one builds machines that way today.


Assignment Problem - multiple tasks, but only one chosen based on their preference (cost)

This can be reduced to minimum-cost flow, for which there are polynomial-time  algorithms.

Build a bipartite graph, with one vertex on the left for each agent, and one vertex on  the right for  each instance of a task.  Tasks are duplicated according to the maximum number of agents they can be assigned to.  For example, if task $i$ can be assigned up to 5 agents, then there will be 5 vertices on the right corresponding to task $i$.  If agent $i$ has a cost of $c_{i,j}$ for task $j$, add an edge of cost $c_{i,j}$ and capacity 1 from the vertex for agent $i$ to each vertex for task $j$.

Also, add a source vertex and an edge of cost 0 and capacity 1  from the source to each left vertex; and add a sink vertex and an edge of cost 0 and capacity 1 from each right vertex to the sink.  Now, find the minimum-cost flow that sends at least $n$ units of flow from the source to the sink, where $n$ is the number of agents.  That will be the solution to your problem.

There are many algorithms for solving minimum-cost flow problems, and even some off-the-shelf tools.  See Wikipedia for some references that will get you started to learn more.


Compression functions are only practical because "The bit strings which occur in practice are far from random"?

First of all, you're right: Multimedia files are represented (more or less) as random files. The reason for that is that those files are already compressed (lossy). Note that mp3, for example, is nothing but a compression algorithm!
A consequence is that further compression will not yield any noticeable compression (and indeed, lossless compression on already compressed (multimedia) files has never been a road to success).

You're also right on your other point: Lossless compression cannot compress on the average. To see that, say, your possible data set consists of $2^n$ different elements. How many bits do you need per file to always be able to distinguish elements from your set? Right, $n$. In total all files will be represented by no less than $n \cdot 2^n$ bits. Now if you represent some of those files by less than $n$ bits, some files will be represented by more than $n$ bits. That's about all there is to say.

In short, lossless compression works because text files are far from random (just consider the letter distribution of my answer and compare the number of e's with the number of z's!), and compressing random data (e.g. already compressed data or encrypted data) does not make any sense.


without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?

Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight $1$ for edges in the original graph, and $B$ (for some $B > 1$ to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most $n$, and otherwise any tour has length at least $n-1+B$. Thus any approximation algorithm with ratio better than $n/(n-1+B)$ would solve HAMILTONIAN-PATH. Choosing $B = 1 + (c-1)n$, we get then any algorithm with ratio better than $1/c$ would solve HAMILTONIAN-PATH. This is true for any $c > 1$, so MIN-TSP-TOUR cannot be approximated to any constant ratio.

Here is where the triangle inequality comes in in Christofides' algorithm. The algorithm is at follows:

Construct a minimum spanning tree $T$.
Find a minimum matching $M$ between the set $O$ of odd-degree vertices in $T$.
Remove edges from $T\cup M$ to obtain a Hamiltonian cycle $H$.

The analysis goes like this. Suppose $H^*$ is a Hamiltonian cycle of weight $w(H)$. Then $w(T) \leq w(H^*)$ and $w(H) \leq w(T \cup M) \leq w(T) + w(M) \leq w(H^*) + w(M)$. So far we haven't used the triangle inequality. Now take $H^*$ and replace paths from adjacent vertices $a,b \in O$ on $H^*$ with direct edges. The triangle inequality implies that the resulting cycle $H^{**}$ satisfies $w(H^{**}) \leq w(H^*)$. We can partition the cycle into two matchings $M_1,M_2$ satisfying $w(M_1) + w(M_2) = w(H^{**})$, and so $w(M) \leq \min(w(M_1),w(M_2)) \leq w(H^{**}) \leq w(H^*)$. We conclude that $w(H) \leq w(H^*) + w(M) \leq 1.5 w(H^*)$.


Construct regular expression that contains the substring

Any string containing $abcba$ is of the form $xabcbay$, where $x,y$ are strings. This string contains an even number of $b$'s iff $xy$ contains an even number of $b$'s iff either $x,y$ both contain an even number of $b$'s, or both contain an odd number of $b$'s. This leads to the following regular expression:
$$
(a+c)^*(b(a+c)^*b(a+c)^*)^*abcba(a+c)^*(b(a+c)^*b(a+c)^*)^* + \\
(a+c)^*b(a+c)^*(b(a+c)^*b(a+c)^*)^*abcba(a+c)^*b(a+c)^*(b(a+c)^*b(a+c)^*)^*
$$


Modeling timing characterists of an architecture

The simple answer is to just build the simplest architecture that gives the results you want. You will have lots of problems anyway, making the system more complex than strictly required is just making more work. And a simple architecture is probably more performant than a more complex one, and easier to work with for further analysis.

Once it is running, check if the performance is enough. If it isn't, measure where it doesn't is up to the task (programmers are notoriously unreliable at estimating that, another reason not to "optimize" before seeing results), then go searching for ways of increasing performance. The most gain can be gotten by architecture changes, then selection of algorithms and data structures, and at the very end local changes (but most of those your compiler will make anyway). Independent of the above, a faster machine might be cheaper than the programmer time required to redo the code.


Why contraction and weakening rules are the upside down?

Contraction is called contraction because it contracts the two hypotheses into one: $A, A$ is contracted into $A$. Weakening is called weakening because it allows one to deduce a weaker fact: $\Gamma \vdash B$ is stronger than $\Gamma, A \vdash B$ since fewer hypotheses are needed to obtain the conclusion. The names come from forward reasoning: deducing facts from other facts. When you're deducing new truths, you can take already-proven truths and add hypotheses or remove duplicated hypotheses.

When you look at contraction from the point of few of backward reasoning, i.e. examining why a fact might be true, then the contraction duplicates a hypothesis. Similarly the weakening rule discards a hypothesis. When you're trying to prove a goal, you can duplicate or discard hypotheses to get a new goal whose truth implies the truth of the original goal.


How to calculate the weight between neurons in ANN?

As far as I can tell, the information provided does not appear to be enough to answer your question, though I confess I am not familiar with what a "unipolar continuous threshold function" is, and it is not clear to me what $f(\text{net}_A$) represents nor what the loss function for this task is.  You might need to talk to your instructor or wherever you got that image from.  You might ask them what a "-" over an edge means.


Halting Problem and Turing Degree and Reduction?

To complete LogicLove's answer, the solution for (1) can be found in a math.se question.

As there are pairs of degrees which have no greatest lower bound, the conditions for a distributive lattice can't be met.


Decidability of dependent typing on primitive recursive languages

Not only is the answer to this question yes, but this is exactly the strategy that modern implementations like Coq and Agda take! To be precise, the type checker has to preform evaluation when deciding definitional equality so it would, if given the right language, be possible to write an infinite loop and ask whether a term was definitionally equal to another term. Because of the way we define definitional equality in most cases, this demands evaluation.
The calculus of constructions (CoC) is actually strongly normalizing. Type checking of CoC is decidable and requires no termination checking. But to make this theory more useful, we add the ability to define inductive types and recursions over them. This way, we get the calculus of inductive constructions (CIC), which Coq is based on.based on). You can view this as a means of adding terms to our language that add computational content that would otherwise not be present.
Note than many inductive types can already be represented in CoC without the aid of CIC, but CoC cannot represent everything CIC can. Coq and Agda both have termination checkers which accept all primitive recursive functions, and both also allow encoding the Ackermann function. You can see more about this in a question I once asked here on a characterization of the class of primitive recursive functions.
Good refrences on Agda's termination checker are

http://www2.tcs.ifi.lmu.de/~abel/foetus/
http://wiki.portal.chalmers.se/agda/pmwiki.php?n=ReferenceManual.TerminationChecker

There is also a lot of work on sized types to provide an alternative to termination checking as well as some work on abstract interpretation based solutions. Currently however, checking for a generalization (see Foetus) of primitive recursion is as far as the state of the art in mainstream implementations goes — at least as far as I am aware.


What are some practical problems which require the use of Kadane's algorithm?

See the Wikipedia article on the maximum subarray problem for applications to genomic sequence analysis, computer vision, and data mining.


Design an algorithm,have polynomial complexity for deciding satisfiability of a 1-conjective Normal Form boolean formula

Most satisfiability algorithms do actually find an assignment for the variables to satisfy the equation, but in your case (a conjunction of single variables) this is not necessary.

When the entire logic formula is just a single conjunction of variables, the only way it is not satisfiable is if it contains both $a$ and $\neg a$. If there is no variable which is contained both positive and negatively in the formula, the formula is satisfiable.


Sorting array with two elements - in place and minimal number of comparisons, lower bound

$n-1$ comparisons are necessary and sufficient. To show that $n-1$ comparisons are necessary, we consider an adversary that always answers "EQUAL". Suppose that an algorithm makes at most $n-2$ comparisons. Construct a comparison graph whose vertices are the array elements and whose edges are the comparisons. Since the graph has at most $n-2$ edges, it is not connected. Let $C_1,C_2$ be two connected components. It is consistent that the value of all elements in $C_1$ is $0$ and that the value of all elements in $C_2$ is $1$. It is also consistent that all elements in $C_1$ are $1$ whereas all elements in $C_2$ are $0$. No monotone ordering of the array is consistent with both options, showing that the algorithm is incorrect.

To show that $n-1$ comparisons are sufficient, consider the algorithm that compares the first element to all other elements. There are three cases to consider:

The first element is equal to all other elements. In this case the array is already sorted.
The first element equals the elements in $S$ and is smaller than the elements in $T$. Thus the first element and the elements in $S$ have the value $0$ and the elements in $T$ have the value $1$, and we can sort the array accordingly.
The first element equals the elements in $S$ and is larger than the elements in $T$. This is symmetric to the previous case.


Counting involving equivalence classes and languages

If you look at two strings in your example $abba$ and $babbb$, they are composed of exactly the symbols from the set $\{a,b\}$, where each symbol appears at least once. So you can reduce  the counting problem in your question to counting the number of subsets of $\{a,b,c,d\}$. Note that one equivalence class would be $\{\lambda\}$ where $\lambda$ denotes the empty string. How many subsets does $\{a,b,c,d\}$ have?


Binary search in log time on a Turing Machine

Can't be done.

Assuming the TM receives its input as $\langle x, A \rangle$ (i.e., $x$ followed by $A$) and that $x$ as well as the array contents are binary encoded, then the asymptotic log-time bound ensures almost all inputs are such that the TM is not even able to read past $x$, let alone search the array. Even if you bound the contents of the array (i.e., a constant number of values, one value per cell), the TM can only read up to the first $\log n$ entries for a list of size $n$; searching for an $x$ strictly larger than those entries will fail.

I am not sure how you intend to represent binary trees (with pointers?). I am sure it is the same case as above.

That being said, there are models which add random access capabilities to TMs, in particular random-access TMs. You might want to look into those.


Can you reduce a precedence graph or do *all* relevant nodes need to be connected

Yes it is necessary.

According to the definition of precedence graph, a directed edge $T_i \longrightarrow T_j$  is created if one of the operations in $T_i$ appears in the schedule before some conflicting operation  in $T_j$.

It is clear from the definition that we have to consider every two transactions separately : $T_1$and $T_2$, $T_1$and $T_3$ and $T_2$ and $T_3$.

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
     | w(x) |
     |      | w(x)

So an edge $T_1 \longrightarrow T_3$ is necessary because w(x) in $T_1$ and w(x) in $T_3$ are two conflicting¹ operations.

 T1  |  T2  |  T3
-----+------+-----
 w(x)|      |
 w(y)|      |
     | w(x) |
     | w(z) |
     |      | w(y)
     |      | w(z)

For this schedule there will be three edges in the precedence graph:$T_1 \longrightarrow T_2$, $T_1 \longrightarrow T_3$ and $T_2 \longrightarrow T_3$.

1.Two operations are conflicting, if they are of different transactions, upon the same datum (data item), and at least one of them is write.


Asymptotic behavior of functions with not analytic expression

Is it safe?  No, of course, it's not safe.  There could always be ways that your experiments are misleading.  Maybe the worst case wasn't triggered by your particular workload or in your particular experiments.  Maybe there's a quadratic term with a small constant, which is negligible for the values of $n$ you tested in your experiments but becomes dominant for very large values of $n$.  You can't rule out those possibilities with experiments.

Are the experiments good enough?  That depends on the community, and for what purpose you want to use them, and what conclusions you want to support.  Can you conclude that the worst-case running time, over all possible inputs, is linear?  No.  Can you conclude that for workloads that are likely to arise in practice, the running time appears to be linear?  Perhaps.  Is this enough to conclude that your system or your method has merit or is a significant contribution over the state of the art?  Quite possibly.

There is no single answer about what is "acceptable".  Instead, I suggest you take a broader, more nuanced view.  Understand the strengths and limits of any method of analysis; understand what conclusions you can and can't support, using those methods; understand what claims you want to be able to make; understand the values of your audience nad the community you are targetting; and go from there.


What are possible uses for cross, back and forward edges after the DFS visit?

Think of the following problem:
Given a directed graph $G = (V,E)$, determine whether there is a pair of vertices $u, v$, s.t $u\neq v$ and $\mathit{and}$ there are at least two $\mathbf{simple}$ paths from $u$ to $v$.

Hint: use the edge labels given by the $DFS$.

Solution:

   If and only if there are any "cross" or "forward" arcs in the tree given by a $DFS$ tour on $G$, then a pair of vertices $u, v$ exists s.t are at least two $\mathbf{simple}$ paths from $u$ to $v$.

Proof:

   1. Suppose no "Cross" or "Forward" Arcs exist. Then the tree given by the $DFS$ is a directed tree, with some "Backwards" arcs. A tree by definition has only one path between every pair of vertices, and below it is shown backwards arcs only add new simple paths.

Consider the backward arc $(u,v)$:

 $\bullet$ for all the ancestors of $v$, it only adds non simple paths.

$\bullet $ for all the descendants of $v$ and ancestors of $u$, denoted by $w$ (vertices between $u$ and $v$ on the tree), it adds one simple path from $w$ to any vertex below (including) $v$ and above (excluding) $w$. All these paths are new because the tree is directed, and all other paths are non-simple, because they contain a cycle.

 $\bullet $ for descendants of $u$, it makes no difference.

2.

 $\bullet$ Suppose a "Cross" arc exists between $(u,v)$. Then $u$ cannot be the root of the tree (the proof is trivial and omitted). Which means the following simple paths exist: $r \rightarrow v$, $r \rightarrow u$, $r \rightarrow u \rightarrow v$

 $\bullet$ Suppose a "Forward" arc exists between $(u,v)$. Then $v$ is a descendant of $u$, but not a child of $u$, therefore there are at least two simple paths from $u$ to $v$.


Computing 'score' of string which preserves < relation

Suppose that your alphabet has size $N$ (say, $N=256$). You can think of each word as being over an alphabet of size $N+1$, with the extra element (first in the order) representing "end of word". Take a short prefix of the word (of some fixed constant size) and think of it as the base $N+1$ representation of a natural number.

As an example, suppose that the alphabet is $A<B$ (in this order), and that we take prefixes of length 2. Consider the strings
$$
A < AA < AAA < B.
$$
We think of these as the numbers $1,11,111,2$ in base 3. Taking prefixes of length 2, we get $10,11,11,20$ (here you see how the extra element is used). The encodings are thus
$$
3 < 4 = 4 < 6.
$$


Reference request: proof that if $L \in DCFL$, then $L \Sigma^* \in DCFL$

One of the early works on DCFL is Seymour Ginsburg, Sheila Greibach: Deterministic context free languages, Information and Control, Volume 9, Issue 6, December 1966, Pages 620–648, doi:10.1016/S0019-9958(66)80019-0

The paper has various closure properties, for instance closure under complement (mind that my old Hopcroft and Ullman book states ".. was observed independently by various people") and closure under quotient with regular languages.

Closure of DCFL under concatenation with regular languages is the result you need, which is Theorem 3.3 from the paper.


Finding a 4-clique among $k$ node groups

First of all, the greedy strategy you outlined does not work. It may be possible that the node with highest degree is in a clique with lower total degree than the clique with the maximum degree.

Second, this problem is clearly in P because we can simply check all $\binom{n}{4} = O(n^4)$ cliques, checking they meet the partition requirement, and keeping track of the one with largest total degree. It's possible there's a more efficient algorithm though, especially considering this naive one does not use the partition information to rule out any cases.


Build-Max-Heap: Why Start i at floor(A.length/2) rather than A.length?

It isn't, neither from a complexity nor from a correctness point of view, however, by starting the counter at $n$ you are doing useless work.

Heapify is a procedure that, if invoked on a node $v$ such that the trees rooted in its children are binary heaps, turns the tree rooted in $v$ into a binary heap. Trees that contain only one node are trivially binary heaps, therefore, you may just start running the algorithm from the first non-leaf node: invoking heapify on the leaves wouldn't have done anything, anyway.


FA for when length of $w$ is $4$ or $w$ contains the substring $01$

The easiest way to construct a deterministic automaton for such a language is to use the product construction:

Construct an automaton for all words of length $4$.
Construct an automaton for all words containing the substring $01$.
Use the product construction to construct an automaton for the union.

If you are allowed to use a nondeterministic automaton, then you can replace the product automaton with a "union automaton", that is, add a new initial state and connect to the the initial states of the two automata with $\epsilon$ transitions.


What does a square mean in a Boolean formula

Ran's comment is correct. This isn't standard notation in proof complexity (the relevant area of TCS), though it might be standard in SAT solving (the relevant applied area). It stands for the empty disjunction.

Semantically, the empty disjunction is the same as contradiction, but the former is a clause whereas the latter is a formula (or sometimes a constant). The usual symbol for contradiction is $\bot$, read bottom.


Is it standard for VMs to run *= computationallyHeavyFunction() if the left hand side is 0?

Optimizing 0 * f(…) is correct only if f has no side effect and its result is known to be finite. If f has side effects, they must be executed even if the result does not matter. If f might return a result such as NaN or infinity then the result of the calculation might be NaN and not 0.

A VM that is optimized for numerical or symbolic calculations and that has access to enough type information to know that f has no side effects and has a finite result would presumably optimize the call away. Any other type of VM would not do this optimization.


First Order interpretation of arbitrary structures as a graph

The following is, as requested, a hint rather than a full answer.  I'll hint at one way of doing the coding; I'll not touch on how to define the queries but those formulas will always be horrible and you'd probably end up describing them in words anyway.  We'll code a structure $\cal{A}$ that has universe $A$ as a graph $G_\cal{A}$. The will contain one vertex for each element of $A$, plus a whole bunch of other vertices that encode the relations and so on.

You can assume a purely relational vocabulary by using standard codings of constants and functions as relations.
Coding is done by adding "gadgets": small graphs that you can recognize. Remember that, for every graph $H$ on $k$ vertices, there is a formula $\varphi_H(x_1, \dots, x_k)$ such that $(G, v_1, \dots, v_k)\vDash \varphi_H$ iff the subgraph of $G$ induced by $v_1, \dots, v_k$ is $H$.
You probably need a way to say "This vertex is an element of $A$." Come up with a gadget, make a copy of the gadget for each element of $A$ and add an edge between the gadget and the vertex coding that element.  (You might not need to do this but it's normally easier to just do it than to prove that it's unnecessary.)
You definitely need a way to say "This tuple $a_1\dots a_r$ is in the $r$-ary relation $R$." Come up with a gadget for each relation and a way to attach each tuple in $R$ to its own copy of the gadget. Remember that the tuple $a_1a_2a_3$ is different from $a_2a_3a_1$ so your coding needs to make those different.

If you don't understand what I mean about gadgets, mouse-over the following for a concrete example. However, the example gives away a lot of the answer, so try not to look at it.

   You could mark a vertex $v\in G_\cal{A}$ as coding an element of $A$ by adding a $k$-clique to your graph, along with an edge from one vertex of the clique to $v$. So, being adjacent to a $k$-clique means a vertex codes an element of $A$. Make $k$ big enough so there are no other $k$-cliques in $G_\cal{A}$.

If you still don't understand, leave a comment and I'll try to explain it better.


Find pixel mapping matrix with minimum iterations

Number the pixels from $0$ to $n^2-1$. Then create $\lceil \log_2n^2\rceil$ many pictures. In the $i$-th picture all pixels are black, if the $i$-th bit in their number is $1$, white otherwise.

Note: If you have $2^k$ colors available, you can choose the color for each pixel based on $k$ successive bits of the number. This will reduce the number of images by a factor of $k$.


Reusing variable in converting grammar to Chomsky Normal Form

"Chomsky normal form" is something a grammar is, rather than the specific procedure used to make it. So nothing prevents you from reusing a symbol like that; the grammar will still be CNF if you do.


P vs NP and Angle Trisection (serious question)

Here is a possible analog of the P vs NP question for straightedge-and-compass constructions.

Suppose that we are given a line with three points $a,b,c$ on it, and consider the following question:

  Given just the line and the points $a,b$, can we construct the point $c$ using a straightedge and compass?

If we are given a construction, then we can verify that it indeed constructs the point $c$. But without such a construction, it is not clear how to check whether the point $c$ can be constructed.

However, this connection is a bit misleading, for various reasons, among which is that it is not completely clear how to specify the input, and what operations are allowed on it; in contrast, the P vs NP question is completely formal.

The P vs NP question is a scaled-down version of other questions in computability theory, whose answer is known. For example:

  Given a C program $P$, does $P$ ever halt?

If $P$ halts, then we can verify it by running $P$ and checking that it eventually halts; you can think of this as a verification process in which the witness is the execution trace of $P$. But without an execution trace, it is not so clear how to determine whether $P$ ever halts. Indeed, Turing proved that no algorithm can determine whether a given C program ever halts.

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question can be stated as follows:

  Is there a polynomial time algorithm to determine whether an input graph is 3-colorable?

(A graph is 3-colorable if we can color its vertices using 3 colors so that the endpoints of each edge get different colors.)

Given a 3-coloring, it is easy to check (in polynomial time) that it is a valid 3-coloring. But without such a 3-coloring, it is not clear how to check whether a given graph is 3-colorable. Indeed, people conjecture that this cannot be done in polynomial time (but it can obviously be done in exponential time, by trying all possible 3-colorings).


What needs led to the implementation of ASCII codes?

Those r "number" systems they represent just numerical values. ASCII is a standard "coding" that include characters

(encode them as digital binary number, for example "A" is represented as 65)

Think of it as a fn that maps each number/character/symbol(enter for ex. has a code that I don't remember now)  to a code number that will be represented to the computer in binary format


What's the best algorithm to find the shortest path between 2 vertices in a graph?

At least in theory, the most appropriate algorithm is breadth-first search (BFS), which you execute by starting from your source vertex $s$. Once the BFS traversal hits your target vertex $t$, you halt and trace back a chain of predecessors originating from $t$. This procedure runs in linear time, which is optimal.

However, from a practical standpoint, the answer might depend on the topology of your graph. For instance, some other linear time procedure like a bidirectional search can be much more efficient but this is more challenging to determine apriori.


Let me write the definition in a little bit more detail.

Suppose that $f(n),g(n)$ are two functions from $\mathbb{N}$ to $\mathbb{R}_+$, that is, they accept as input a natural number, and return as output a positive real number.
We say that $f(n) = O(g(n))$ if there exist $n_0 \in \mathbb{N}$ and $C \in \mathbb{R}_+$ such that for all $n \geq n_0$,
$$ f(n) \leq Cg(n). $$

In order to show that $f(n) = O(g(n))$, you have to find $n_0$ and $C$ such that for all $n \geq n_0$ it holds that $f(n) \leq Cg(n)$. You can choose whatever $n_0,C$ you want as long as the condition holds. It turns out that for this definition, we can always take $n_0 = 1$ (for other variants of the definition, this no longer holds). So you only have to find a positive constant $C > 0$ such that for all $n \geq 1$ it holds that
$$ f(n) \leq Cg(n). $$
(This assumes that the first natural number is 1 rather than 0.)
Now we can answer your question:

$n$ is the argument of the functions $f,g$.
$n_0$ is the point beyond which the inequality $f(n) \leq C g(n)$ should hold. When proving that $f(n) = O(g(n))$, you get to choose $n_0$. In most cases you can just take $n_0 = 1$.

For the curious: why do we need $n_0$? Sometimes we would like to accommodate functions which are not strictly positive, but just eventually positive. For example, if 0 is a natural number (in contrast to the convention used above) then $n^2$ is not strictly positive, since it vanishes at $n = 0$. Therefore $n = O(n^2)$ is only true if we allow to "skip" $n = 0$, which we do by choosing $n_0 = 1$.


Outputting numbers within a range that are not in a list

Facetious answer: all the sizes involved are constant, so a straightforward algorithm for this will run in $O(1)$.

Serious answer: with such small numbers involved, getting too elaborate may just slow you down. Simplicity is your friend.

let found be an array [0..255]
found ← [false, false, false...]

for i ← [1..100]:
    value ← A[i]
    if found[value] is true:
        there was a repeat
    found[value] ← true

for j ← [0..255]:
    if found[value] is false:
        j was not in the list

This runs in $O(n+k)$ time and $O(k)$ space (where $n$ is the number of elements in the array and $k$ is the maximum size of those elements). I don't believe it's possible to do better.


Finding a Simple Distribution In a Binary String

TL;DR: use maximum likelihood and discrete optimization.

Evaluating candidate models: the maximum likelihood principle

If you have a candidate model, you can evaluate how well it fits the data using the maximum likelihood principle.

If $M$ is a model and $x$ is a string, let $P(x|M)$ denote the probability of outputting string $x$ when $M$ is the true model.  Here I assume a generative model that produces $x$ as follows: at each step, it randomly picks one term $g_i \times n_i$ from $M$, appends $n_i$ copies of the string $g_i$ to the output, and repeats until some stopping point (say, stops once we've generated a string of fixed length).

Of course in practice we have the reverse problem: we have observed a fixed string $x$, and want to infer $M$.  Now we'll treat the observation $x$ as fixed.  We define the likelihood of $M$ to be $L(M) = P(x|M)$.  If we have observed multiple strings $x_1,\dots,x_m$, then we define the likelihood of $M$ to be $L(M) = P(x_1|M) \times \cdots \times P(x_m|M)$.

The intuition is: models with larger likelihood fit the data better.  So, if you have a choice of multiple models, choose the one with the largest likelihood -- that's the one that seems most consistent with the data.

In practice, for computational reasons, we often deal with the log-likelihood, $\log L(M)$.  We choose the model whose log-likelihood is largest.  Since the log is monotone, this doesn't change anything fundamental.

if you're comparing a simple model to a complex model, this introduces the risk of overfitting.  The likelihood alone doesn't account for Occam's razor: the principle that, all else being equal, simpler models are more likely to represent the truth.  This can be fixed by introducing some kind of regularization.

Finally, note that the likelihood of a model can be computed efficiently using dynamic programming.  We each prefix $w$ of $x$, we compute $L(w)$ in terms of shorter prefixes, starting from shorter prefixes to longer prefixes, until we have computed $L(x)$.  If you don't immediately see how to do this computation, ask a separate question; it's a standard dynamic programming exercise.  If you're dealing with long strings, you might want to compute using log-likelihoods rather than likelihoods, to avoid underflow.

Fixed-length tokens

If all tokens have the same length, it's probably fairly easy to find a good model.  Assume know the length $\ell$ of all tokens in the model; if we don't, we can try each possibility for $\ell$, one at a time, and take the one that yields the best model.

Since we know the length $\ell$, we can divide the string $x$ up into tokens of length $\ell$.  In this way we can see the set of all tokens that appear in $x$, say $t_1,\dots,t_k$.  Now we know that the model must be of the form

$$M = \{t_1 \times n_1, \dots, t_k \times n_k\}$$

and we merely need to infer the numbers $n_1,\dots,n_k$.

Let's focus on the token $t_1$ and see how to infer $n_1$.  We can find all occurrences of $t_1$ in $x$, and combine them into sequences of contiguous repeats, and let $S_1$ denote the set of repeat lengths.  For instance, if at one place we see $t_1$ repeated 3 times consecutively, and at another place we see $t_1$ repeated 9 times consecutively, then we have $S_1 = \{3,9\}$.  At this point we simply take $n_1 = \gcd S_1$, i.e., $n_1$ is the largest number that divides every element of $S_1$.

We'll of course repeat this for each token $t_i$.  We end up with a complete model, as desired.

A technical detail: This assumes that each token $t_i$ is listed only once in $M$, with a single repeat-factor $n_i$.  In other words, it assumes the model is allowed to look like $\{00 \times 4\}$ but not $\{00 \times 2, 00 \times 3\}$ (the latter has the token $00$ with two different repeat-factors).  If you want to consider the latter kind of model, the problem reduces to finding a set of repeat-factors $R_1$ such that every element of $S_1$ can be expressed as a linear combination of $R_1$.  The optimal solution will depend on the form of regularization you use; without regularization, the optimal solution will always be to simply take $R_1$ to have a single element, $R_= \{\gcd S_1\}$. So if you want to consider models where the same token appears twice, you'll need to specify a particular form of regularization (ask a new question).  For now, I'll assume such models aren't of interest.

So this shows how to solve the problem, in the easy case where all tokens have the same length.

Variable-length tokens

Handling models where the lengths of the tokens are not all the same looks much more challenging.  I can suggest one possible approach, but the best approach will probably depend on the parameter settings you're encountering in practice.

I suggest reducing this to a discrete  optimization problem.  In particular, I suggest you identify a set of tokens $t_1,\dots,t_k$ that you're confident will be a superset of the ones in the real model, and then use optimization methods to solve for the repeat-factors $n_1,\dots,n_k$ that maximize the likelihood of the model.

In more detail: Fix the set of $t_1,\dots,t_k$.  Now the model looks like

$$M = \{t_1 \times n_1, \dots, t_k \times n_k\}$$

where the $t_i$'s are known and the $n_i$'s are unknown (variables).  Consequently we can think of the likelihood $L(M)$ as a function of the $n_i$'s: given any candidate values for $n_1,\dots,n_k$, we can compute $L(M)$ using dynamic programming.

So, I'd suggest you use some existing optimization strategy to find $n_1,\dots,n_k \in \mathbb{N}$ that maximize $L(M)$.  A natural approach is probably some form of local search, e.g., hillclimbing, hillclimbing with random restarts, or simulated annealing.  A suggestion for a set of "local moves" would be to pick a single $n_i$ and change it via one of the following operations: multiply $n_i$ by a small prime number; divide $n_i$ by a small prime divisor of it; set $n_i$ to zero; change $n_i$ from zero to a small number; increment $n_i$; decrement $n_i$.

How do we find the set $t_1,\dots,t_k$ of tokens?  Here a convenient fact is that we don't have to get this set exactly right; it suffices for it to be a superset of the true set of tokens in the actual model.  In particular, setting $n_i=0$ is equivalent to removing the token $t_i$ from the model entirely.  So, we can choose a larger-than-necessary set of tokens $t_1,\dots,t_k$ and let the optimization routine effectively solve for which tokens should be retained and which should be eliminated.  One heuristic would be to choose $t_1,\dots,t_k$ to be the set of all bit-strings of a certain range of lengths (e.g., all bit-strings of length 2 or 3).  Another heuristic would be to use some kind of filtering condition: use the set of all bit-strings $t$ that appear at least some minimum number of times in $x$.  The nice thing is that we can try each of these choices in turn, apply the optimizer to each, get a list of candidate models, and choose the best one (using the maximum-likelihood principle).  For instance, it might not be clear how to choose a threshold for the filtering, but we can try multiple values in a exponentially decreasing sequence and keep the best model obtained.

Similarly, it's also possible to come up with heuristics for the initial values of $n_1,\dots,n_k$ to feed to the optimizer (this will help some optimizers converge to a better solution).  For instance, for each token $t_i$ and each candidate repeat-factor $r$, you could count the number of times that $t_i$ appears repeated $r$ times in a row, then choose the value of $r$ that has the highest count as the initial guess for $n_i$.

How well will this work?  I don't know.  It will probably depend a lot on the parameters of the problem instances you run into in practice.  I would suggest you try it on your data sets, with several different optimization methods and fiddling with the parameters a bit.  If it doesn't work, ask another question where you show us what you've tried, and also show us the typical range of values for the most important parameters: the number of tokens in the model ($k$), the range of lengths of the tokens themselves, the range of values of the repeat-factors $n_i$, the length of the string $x$.


Planar graphs of bounded degree: mixing time = cover time?

The answer turns out to be no. A counterexample, kindly suggested to me by Balász Gerencsér, is a $\sqrt{N}$ by $\sqrt{N}$ grid, with a path of length $\sqrt{N}$ glued to it. One can show that

the mixing time of a simple random walk on this graph is $O(N\log N)$ (by combining Cheeger's inequality and the Spielman-Teng [1] bound on the spectral gap)
the cover time of a simple random walk on this graph is $\Omega(N^{3/2})$ (by combining Matthews method with an expression of the hitting time using effective resistance)

[1] Spielman, Daniel A., and Shang-Hua Teng. "Spectral partitioning works: Planar graphs and finite element meshes." Linear Algebra and its Applications 421.2-3 (2007): 284-305.


Generating numbers to be averaged efficiently

A reasonable solution is to first generate a random point in the simplex
$$ x_1 + \cdots + x_K = 1, \qquad x_1,\ldots,x_n \geq 0. $$
Check out this question for several ways to do this. Then take
$$
P_i = \frac{P}{\alpha_i} x_i.
$$
This should give you a uniformly random point in the geometric body you are interested in
$$
\sum_{i=1}^K \alpha_i P_i = P.
$$


$O(n \log n)$ simple polygon triangulation via divide and conquer

Garey, Johnson, Preparata and Tarjan came up with a simple $O(n\log n)$ algorithm back in 1978. It is described in many lecture notes, for example these lecture notes of Piotr Indyk.


Logic behind O(n) solution for 'Maximum length sub-array having given sum'

This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way.

Initialise sum = 0 and maxLen = 0.
Create a hash table having (sum, index) tuples.
For i = 0 to n-1, perform the following steps:

Set sum = sum + arr[i].
If sum == k, update maxLen = i+1, continue from here to next iteration.
Check whether sum is present in the hash table or not. If not present, then add it to the hash table as (sum, i) pair.
Check if (sum-k) is present in the hash table or not. If present, then obtain (sum-k, index) from the hash table. If maxLen < (i-index), then update maxLen = (i-index).
Return maxLen.

If sum == k at case 3.3, then we know that the sub-array [a[0],...,a[i]] is the maximum-length sub-array whose sum is k. Otherwise, we continue to 3.3. If there was no sub-array until now whose sum we equal to the current sum, then we add (sum, i) to the hash table. The reason we don't overwrite existing entries will become apparent at the end.

We now continue to 3.4. If we came across a sub-array S whose sum was sum - k, then there must be pair of the form (sum - k, index) in the hash table. S is therefore the sub-array of the form [a[0], ..., a[index]].

We obtain a new sub-array [a[index + 1], ..., a[i]] whose sum is k and whose length is i - index as follows: Remove all elements in S from the sub-array [a[0], ..., a[i]]. Its sum must be sum - (sum - k) = k. Now the question is whether the length of the new sub-array i - index > maxLen. If it is, set maxLen = i - index.

Now we can see why we didn't update existing entries in 3.3. We do not want to add larger arrays (greater index) for a given sum. This would have made i - index smaller.

This is a polynomial-time algorithm, as we look at each element exactly once, and the hash table accesses are also constant time.


If A is reducible to its complement, is the converse true as well?

In general whenever $A\le_m B$ via computable function $f$, we automatically have $\bar{A}\le_m \bar{B}$ via the same $f$. The reason is that $x\in A\iff f(x) \in B$ implies that $x \in \bar{A} \iff f(x) \in \bar{B}$.


Some useful guidelines for writing are:

Who is my audience?
Will my audience understand what I am writing?
Will my usage of language be distracting or otherwise take attention away from the message I'm trying to make?

In this case, your audience is probably another computer scientist who has at least some knowledge of your area.  Therefore, yes, I would expect that another computer scientist will understand your meaning if you write "XORing" or "XORed".  Also, it's common enough that I don't think it will be distracting.  Whether it's too information is perhaps a bit subjective, but I don't view it as too informal.

I've seen it both ways: "xoring" and "XORing".  Personally, I find the all-caps jarring, so my eye prefers "xoring", but I think that is a matter of taste.

Note that "ciphertext" is normally spelled that as one word, and with an "i", not a "y".  Right: "ciphertext".  Wrong: "cyphertext", "cypher text", "cipher text".


How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method?

You could try upper and lower bounding the work done in your recurrence tree by two other simpler recurrences.

For instance, this is the function/rate by which your recurrence input decreases at each level: $$f(n) = \sqrt{n-1} + 2$$

We can find a function the decreases faster, for example

$$f_1(n) = \sqrt{n} \leq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

We can also find a function that decreases slower, for example

$$f_2(n) = 2\sqrt{n} \geq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

Thus with $f_1(n) \leq f(n) \leq f_2(n)$ we can construct two other recurrences based on these new functions:

$$\begin{align*}
T_1(n) & = 2T_1(\sqrt{n}) + 1\\
T_2(n) & = 2T_2(2\sqrt{n}) + 1\\
\end{align*}$$

We can then bound our original recurrence by these:

$$T_1(n) \leq T(n) \leq T_2(n)$$

So if you can solve these recurrences, then you can bound $T(n)$ appropriately, because these will lower bound and upper bound the depth of the recursion tree respectively.

I wanted to work through this a bit further for my own satisfaction. Not quite a recursion tree analysis, but I think this function is interesting so I worked through it.

The first $T_1$ we can solve relatively easily with a domain transform:

$$\begin{align*}
T_1(n)       & = 2T_1(\sqrt{n}) + 1\\
T_1(2^{2^k}) & = 2T_1(2^{2^{k-1}}) + 1\\
S(k)         & = 2S(k-1) + 1\\
             & = \Theta(2^k)\\
T_1(n)         & = \Theta(2^{\log \log n})\\
             & = \Theta(\log n)
\end{align*}$$

The second $T_2$ is a little trickier, but not much. Let's unwrap this a bit:

$$\begin{align*}
T_2(n) &= 2T_2(2\sqrt{n}) + 1\\
       &= 2\left(2T_2(2\sqrt{2\sqrt{n}}) + 1\right) + 1\\
       &= 4T_2(2^{3/2} \cdot n^{1/4}) + 3\\
       &= 4\left(2T_2(2 \cdot (2^{3/2} \cdot n^{1/4})^{1/2}) + 1\right) + 3\\
       &= 8T_2(2^{7/4} \cdot n^{1/8}) + 7\\
       &= \vdots
\end{align*}$$
The pattern starts to emerge and we can perform another domain transform (obviously, to be formal you should prove that the pattern holds by induction, but I'm omitting that).

Let $n = 4^{2^k + 1}$ and when we apply $2 \sqrt{n}$ we get:

$$\begin{align*}
2 \sqrt{4^{2^k + 1}} & = 2 \sqrt{4} \sqrt{4^{2^k}}\\
                     & = 4 \cdot 4^{2^{k-1}}\\
                     & = 4^{2^{k-1} + 1}
\end{align*}$$

Now with this we do the domain transform:
$$\begin{align*}
T_2(n) & = 2 T_2(2 \sqrt{n}) + 1 \\
T_2(4^{2^k + 1}) & = 2 T_2( 2 \sqrt{4^{2^k + 1}}) + 1\\
S(k) & = 2 S(k-1) + 1\\
     & = \Theta(2^k)\\
T_2(n) & = \Theta(2^{\log_2(\log_4(n) - 1)})\\
       & = \Theta(\log n)
\end{align*}$$

With this we see:

$$\begin{align*}
T_1(n) &\leq T(n) \leq T_2(n) & \forall n \geq 4\\
c_1 \log n &\leq T(n) \leq c_2 \log n & \forall n \geq 4\\
\implies T(n) & = \Theta(\log n)
\end{align*}$$


Can I have actions that, if taken, cannot be taken again in the following N timesteps?

This is not a limitation.  Which actions are valid can depend on the current state of the system.

To enforce your requirement (changing speed at time T means you can't change again until time T+N), you can add additional information to the state: basically, add how long ago was the last change (where if it's more than N steps ago, you don't keep track of how long, just that it was long enough that a change is now allowed).


Are the Confabulation Theories of Thaler and Hecht-Nielsen Isomorphic?

I don't think they map onto each other, aside from RHN's brief discussion of thalamo-cortical loops, the inspiration for SLT's so-called "Creativity Machines." In SLT's architectures, compelling/cogent solution patterns are sought within a stream of novel activation patterns (i.e., confabulations) driven by various forms of internal disturbances to biological neural nets. RHN's definition of cogency is obviously not the same. The mathematics of SLT's model are scattered over several patents and papers, but the following might provide an overview: Predicting ultra-hard binary compounds via cascaded auto- and hetero-associative neural networks, Journal of Alloys and Compounds, 279(1998), 47-59, Synaptic Perturbation and Consciousness, International Journal of Machine Consciousness, 6(2):75-107, 2014, Cycles of Insanity and Creativity within Contemplative Neural Systems, Medical Hypotheses, 94:138-147, Elsevier, 2016, and Pattern Turnover within Synaptically Perturbed Neural Systems, Procedia Computer Science, 88, Elsevier, 2016.


Proving that Hamiltonian Cycle is reducible to a travelling problem?

Basically, Hamiltonian Cycle is the parcel problem with just one driver. To reduce Hamiltonian Cycle to the parcel problem with two drivers, you get one of the drivers to solve your Hamiltonian Cycle problem, and you make enough work for the other driver that they can't "cheat" by helping the first driver (but not so much work that the first driver has to help the second one).


Quicksort vs. insertion sort on linked list: performance

The problem is that the analysis of Quicksort, as you have implemented it, assumes that accessing any element can be done at a constant cost, i.e. in $\mathcal O(1)$. This is not the case with linked lists.

Note that at the top of the while (right > left) { loop in your code, you cycle through all the elements until left and then repeatedly cycle through all the elements adjusting right. While in Quicksort this should just cost at most $\mathcal O(n)$, in your case it costs at most $\mathcal O(N^2)$, where $n$ is the current level of recursion and $N$ is the total number of elements.

As Louis pointed out in the comments below, there is a linked list analogue of Quicksort, but it needs to be implemented quite differently from what you did.

The bottom line: Linked lists are not arrays, and algorithms that will work well on arrays will not necessarily work well on linked lists. There are several good books on algorithms out there that will point you to good algorithms for each case.

Update

The code in the question has now been modified to reflect the implementation described by Louis below. There are still potential inefficiencies, however, in the selection of the pivot. In essence, any single operation inside the main loop which is not $\mathcal O(1)$ will mess-up the asymptotic behavior.

Oh, and creating new lists in every level of recursion is probably not extremely efficient either.


How to define a path between two sets of vertices?

An $A$-$B$ path is a path that starts at some $a \in A$ and ends at some $b \in B$.


Big O: Analyzing the time complexity of an $O(n \log n)$-algorithm

Let's denote by $C(n)$ the number of comparisons performed on an input of length $n$ (later on I will comment more on this definition). The assumption that the number of comparisons roughly doubles when doubling the input size translates to $C(2n) \approx 2 C(n)$. This is not a precise statement, so let us take it to mean that
$$
\lim_{n\to\infty} \frac{C(2n)}{C(n)} = 2.
$$
There are many functions satisfying this statement. Some examples are $n (\log n)^k$, for any value of $k$. This condition cannot distinguish between algorithms with a linear number of comparisons and those with $n\log n$ or $n\log^2 n$ comparisons, and in particular cannot imply that quicksort uses $O(n\log n)$ comparisons.

Let $D(n) = \log[C(n)/n]$, so that
$$
\lim_{n\to\infty} [D(2n) - D(n)] = 0.
$$
What we can conclude is that $D(n) = o(\log n)$, which translates to $C(n) = n 2^{o(\log n)}$.

Another problem with your analysis is that the number of comparisons could depend on the input, not only on the input size. In other words, $C(n)$ is not well-defined. It is known that quicksort has worst case number of comparisons $\Omega(n^2)$, but the average number of comparisons (over a random permutation) is only $\Theta(n\log n)$. We usually take $C(n)$ to be either the worst case number of comparisons or the average number of comparisons (for a random permutation).

Yet another problem is that it's not clear how to establish $C(2n)/C(n) \to 2$. Is this the result of an experiment, a heuristic calculation, or a formal proof? You don't make it clear. Experiments might show that $C(2n) \approx 2C(n)$ for small $n$, but the asymptotic behavior might be different; $C(2n)/C(n)$ might grow slowly, but eventually tend to infinity, for example.