Theoretical CSPs where (in)equality constraints can be expressed as a single constraint?

In complexity theory, CSPs are usually specified as a set of allowed predicates. If the (finite) domain is $D$, a predicate of arity $d$ is an arbitrary subset of $D^d$ of allowed values. In particular, equality (or inequality) is a predicate of arity 2.

This is the point of view taken in Schaefer's dichotomy theorem as well as the more recent universal algebra approach (see for example a short survey by Libor Barto). Another example is the celebrated Raghavendra's theorem, which states that assuming the unique games conjecture, every CSP can be approximated optimally using semidefinite programming.


Defining a context-free grammar for $\{w \in \{0, 1\}^* : \#_0(w) = \#_1(w)\}$

Your grammar does work. And you are correct in assuming that induction is a worthwile proof-technique. As a hint, you can use the following induction hypothesis:

IH: All the words of length at most $n$ that can be derived from $S$ have an equal amount of $0$'s and $1$'s.

Can you fill in the anchor and step from here?

As D.W. pointed out, the above is only enough to prove that the grammar will not produce any wrong words, or $L(G) \subseteq L$. In order to complete the proof, you also need to show that $L \subseteq L(G)$, i.e. all the words in the language are generated by the grammar.

For this part you can try an induction with the hypothesis

IH: All the words of length at most $n$ that have an equal amount of $0$'s and $1$'s can be derived from $S$.

(Of course, you can combine these two inductions, but having them seperate may be easier to handle if you are unexperienced.)


Why did RSA encryption become popular for key exchange?

There is no strong technical reason.  We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA.

So why RSA?  As far as I can tell, non-technical historical reasons dominated.  RSA was patented and there was a company behind it, marketing and advocating for RSA.  Also, there were good libraries, and RSA was easy to understand and familiar to developers.  For these reasons, RSA was chosen, and once it was the popular choice, it stayed that way due to inertia.

These days, the main driver that has caused an increase of usage of Diffie-Hellman is the desire for perfect forward secrecy, something that is easy to achieve by using Diffie-Hellman but is slower with RSA.

Incidentally: It's Diffie-Hellman key exchange, not Diffie-Hellman secret sharing.  Secret sharing is something else entirely.


Determining which states in a transition system satisfy a specific CTL formula

A hint that might put you in the right direction:
Note that $\exists Xc$ (where $X$ is the "next" operator) holds in every state from which there exists a neighbor with $c$. Thus, for example, $1\models \exists Xc$.

Now, $\forall (\phi U \psi)$ holds if in all computations $\phi$ holds until $\psi$ holds. In particular, every state that satisfies $\psi$ also satisfies $\forall (\phi U \psi)$, since the eventuality holds immediately.

Thus, $1$ satisfies the formula. See if you can complete the rest of them now.


Is there any decision problem not in NPH but can be reduced to a NPH problem?

Assuming you're using many-one reductions, $\emptyset$ and $\Sigma^*$ are not NP-hard (exercise: prove this!), but they can be reduced to any NP-hard problem. Therefore, the statement, "one can show that a problem $A$ is in NPH by giving a reduction from $A$ to a NPH problem $B$" is false.


SSTF disk scheduling algorithm? What if lowest seek times are equal in either direction?

Short answer: Depends on implementation.

Long answer: Ties could be broken randomly, or some fixed direction might be preferred. A popular strategy is to select that position first which does not require the head to change direction (since changing direction could take more time). So suppose that the head has moved from 20 to 25, it might prefer 45 next instead of 5 (since it was going towards the higher side). It could also depend on what the further instructions are going to be. Basically, the answer depends on what tie-breaking policy is selected in the implementation, and how complicated the implementation can be.


Measuring Complexity of Boolean Satisfiability Problem

The boolean satisfiability problem (SAT) involves finding a satisfying truth assignment for a set of clauses $C$ over the boolean variables $V=\{v_1, v_2, ..., v_n\}$ so that each clause in $C$ contains at least one true literal. Since $V$ contains $n$ variables and each of these variables can only have $2$ different values (i.e., true or false), the total number of possibilities to be tested is $2^n$. We don't know how to solve SAT in polynomial time (since SAT is NP-complete); therefore, all solvers take exponential time in the worst case. Fortunately, however, there exist several ways to prune the search space.

  Wouldn't the complexity be better measured in terms of how complex the formula is?

The importance of the SAT problem lies in that every decision problem in NP can be reduced to SAT for CNF formulas. Other restricted versions of SAT exist (such as 3-SAT, Horn-SAT, and XOR-SAT); these restricted versions can be either in P or NP depending on the restriction (see Schaefer's dichotomy theorem). Regardless of this, note that problems in NP (such as SAT) are characterized by solutions (in the case of SAT, truth assignments) that can be verified in polynomial time.


Efficient search for solving a Jigsaw Puzzle?

Seems like your heuristic needs to incorporate the distribution of the edge types to be optimal. Here's an idea:

Form a matrix the size of the puzzle's dimensions. Each cell indicates the proportion of remaining pieces that can be fit there on the next iteration without conflicting. At the beginning, the corners of the matrix will be $4$ (only four corner pieces), edges $2(w+h-4)$, and interior $wh-2(w+h-4)$. You can indicate filled cells with a large value, like infinity. Select the set of cells with minimum values as candidates for the next piece. Of these cells, select the piece that decreases the adjacent, unassigned cells by the most amount (use "min" of adjacent cells for the score).

This will ensure you explore the paths that have highest probability of conflicting first. If the first piece you place is incorrect, you want to find if it is incorrect as soon as possible. Likewise, you want to select the first piece to be the one with the least number of choices.

When the min value of the matrix is zero, you know there was an incorrect piece lain somewhere. In that case backtrack, decrease the proportion for the backtracked cell (since now we have eliminated one choice), and begin the iteration again. The backtracked cell will have the minimum value still, of course; so you will simply go on to trying the next piece in the candidate list.

Tentatively, I'd say on average the algorithm would propagate out from the four corners in a spiraling fashion, until two of the corner blocks connect. Then I suspect it would favor building off the connecting block. It will factor in the candidate probabilities, so for specific puzzles the paths it takes will vary.

(You'll need a specialized data structure to store the best candidates list. Could experiment with a blacklist instead. Or could try simply keeping a counter for how many conflicting pieces you tried for a cell, and then recreate the sorted list each time you need to backtrack)


How to understand the complexity of Kruskal implemented with Quick-Union by rank and path compression?

You are absolutely right.  There is nothing wrong with your reasoning.

The running time of Kruskal's algorithm, when implemented in the way you describe, is $O(m \log m)$, or equivalently, $O(m \log n)$.  If the book says its running time is $O((m+n) G(n))$, the book is wrong; that doesn't take into account the time to sort the edges by weight.

If you look at other sources I think you'll find that they correctly report the running time of Kruskal's algorithm.


Understanding the relations between O(g(n)), Θ(g(n)) and Ω(g(n))

Aren't $\Omega(g(n))$ supposed to tell best running time?

Not at all. It just means that for all large enough $n$, there exist inputs of size $n$ where the algorithm takes time at least proportional to $g(n)$.

  Can you please explain why $\Omega(n^2)$ is possible for insertion sort when it should be $\Omega(n)$?

The worst-case running time of insertion sort is $\Omega(n^2)$ because for all $n$, there exist inputs of size $n$ where it takes time proportional to $n^2$.

The running time of insertion sort in general is not always $\Omega(n^2)$, as you observed; it depends on the input. But the worst-case running time (which does not depend on the input, only on $n$) is $\Omega(n^2)$.


As mentioned, the body of the simple loop is run in $O(n)$. As a loop iterates over the body $n$ time (probably), the time complexity of the loop is $O(n^2)$. When you run the loop $n-1$ times, the time complexity would be $O(n^3)$.


Is the following extension of finite state automata studied?

Assuming $k$ can be any integer, then this can be formalized as a blind one-counter automaton. Usually these automata accept on final state when its counter is zero, but we can easily model your acceptance type if you allow $\epsilon$ transitions (that do not consume input). If I am not mistaken, like with finite state automata, one can get rid of the $\epsilon$, but that is a non-trivial result.

There are several types of one-counter automata. In the most general form they are allowed to test whether the value of the counter equals zero.
The languages they accept are a strict subset of the context-free languages.

The model you are probably looking for is called blind, it cannot test for zero, except as the final test for acceptance at the end of the computation.


Extended grammar form (backus-naur) and simple grammar forms equivalence

Show that given a derivation in one grammar, there is a corresponding derivation in the other grammar which derives the same word. You might find it easier to work with parse trees instead of just derivations.

In the case of optional brackets, this is rather easy. Let us consider your example of a grammar with derivation rule $A \to X[Y]Z$ which is replaced by the derivation rules $A \to XZ$ and $A \to XYZ$. Given a derivation in the original grammar, each application of $A \to X[Y]Z$ replaces $A$ by $XZ$ of by $XYZ$. In the former case, we can simulate this in the new grammar using $A \to XZ$, and in the latter by $A \to XYZ$. Conversely, given a derivation in the new grammar, we can replace each application of the rules $A \to XZ$ and $A \to XYZ$ by an application of $A \to X[Y]Z$.

The case of braces is more complicated. One direction is easy – given a derivation in the original grammar, you can convert it to an equivalent derivation in the new grammar by replacing an application of $A \to X \{YZ\}$ by an equivalent derivation using only the rules $A \to XB$ and $B \to YZB \mid \epsilon$. In the other direction, you have to first show that if $B$ appears in a parse tree, then you can associate with it a path in the tree which corresponds to a derivation of the form $B \to YZB \to (YZ)^2B \to \cdots \to (YZ)^k$ for some $k \geq 0$. Given that, every application of $A \to XB$ can be associated with a path corresponding to a derivation $A \to^* X(YZ)^k$, which can be implemented in the old grammar by the rule $A \to X \{YZ\}$.

In the last paragraph I have been vague about some association of vertices in the parse tree to a path and to a derivation, which really amounts do a decomposition of all legal parse trees. These concepts will have to be formalized in a formal proof of equivalence.


Prove that this family of hash function is $3$-wise independent, but not $4$-wise independent

Hint for refuting 4-wise independence: Suppose for simplicity that $c = 2$, pick some $\alpha \neq \beta$ of length $r$, and consider the four inputs $(\alpha,\alpha),(\alpha,\beta),(\beta,\alpha),(\beta,\beta)$.

Hint for proving 3-wise independence: Let the three inputs be $x,y,z$. If there is some coordinate $i$ such that $x_i,y_i,z_i$ are all different then we are done. Otherwise, without loss of generality there are coordinates $i,j$ such that $x_i = y_i \neq z_i$ and $x_j = z_j \neq y_j$, and we are again done.


Undecidability: writing a symbol on Turing Machine's tape

First take a Arbitrary Turing Machine M and modify it so that on stopping state it will first write a new symbol $\phi$ that it won't write at any other time.

If you can decide that Machine M' will write that symbol then you can decide whether machine M halted.


Proving grammar only generate strings that is multiple of 3

Hint: num' generates (1) numbers of even length which are divisible by 3 and (2) numbers of odd length which equal 1 mod 3. For the rule num → 10 num' 01, consider the parity of the length of the number generated by num'.


Upper bound $T(n) = 9T(\sqrt[3]{n}) + O(1)$

You can solve this using the master theorem, whose proof uses a recursion tree argument.

Define $S(n) = T(2^n)$. The main observation is that $\sqrt[3]{2^n} = 2^{n/3}$, and so
$$ S(n) = 9S(n/3) + O(1). $$
The solution is $S(n) = \Theta(n^2)$, and so
$$ T(n) = S(\log n) = \Theta(\log^2 n).$$

You can also open the recurrence directly, obtaining
$$
T(n) \propto 1 + 9n^{1/3} + 9^2 n^{1/3^2} + 9^3 n^{1/3^3} + \cdots.
$$
The general term is $9^i n^{1/3^i}$. The recurrence will terminate when $n^{1/3^i} \approx 1$, which happens when $3^i \approx \log n$, that is, when $i \approx \log_3 \log n$. For this value of $i$, $$ 9^i = 3^{2\log_3 \log n} = \log^2 n. $$
This is the value of the bottom level of the tree. The contribution of the other levels is negligible in comparison, which is something you have to prove by calculation.


It's just a colloquialism.  It means, you keep a set of states that have been marked.  Initially the set is empty.  When you mark a state, you add it to that set.


Equivalence of data-flow analysis, abstract interpretation and type inference?

Data flow analysis and type inference are specific instances of abstract interpretation.

Data flow analysis and abstract interpretation look similar since they are both about computing a fix point. Data flow analyses typically have finite-height abstract domains which ensures termination. In general, abstract interpretation does not assume such abstract domains; to deal with infinite height domains abstract interpretation uses techniques of widening and narrowing.

It turns out that type inference is also about fix-point computation, although that is far from obvious, imo. Here is a paper that explicitly shows that types are abstract interpretations: paper. Basically, types are seen as an abstraction of program concrete semantics. In Hindley-Milner type system, for instance, abstract domain of types is of infinite height and computing a (most general) type using unification is essentially performing a (very imprecise) widening operation.


How to check if DFA is actually a correct model of the intended system?

If you want a guarantee, then yes, verification is the only approach.  That's pretty much the definition of what verification means.

If you want a heuristic check, there are a number of testing methods based on synthesizing test cases (perhaps based on the DFA) and then checking that the vending machine's actual behavior on those test cases matches your DFA's.


Which textbook can I use after a high school CS course?

Personally, I recommend either Algorithms by Dasgupta, Papadimitriou, and Vazirani, or The Algorithm Design Manual by Skiena.

The Algorithm Design Manual is super-practical and full of excellent pragmatic advice, useful stories, and is well-written and easy to read.  If you want to help get ready for programming contests, I strongly recommend that one.

I think Dasgupta has a better introduction from the perspective of learning the conceptual material, the theory, the proofs underneath the algorithms, etc.  So, if you want to learn the theory, I recommend Dasgupta.

You won't go wrong with either; they are both outstanding.

Personally, I think they are better than Cormen.  I learned from Cormen, and it's a perfectly fine book, but it can be a bit dense in places and a bit challenging to learn from, so it wouldn't be my first recommendation.  Still, it's a reasonable contender and you wouldn't be led astray by it; I just think the others are better.


What does $\cdot$ mean as a notation with complexity classes?

Reading Toda's original paper, it's not clear that a general application of $\cdot$ has meaning, however it may have been extended later.

Toda introduces three operators: $\oplus\cdot$, $\mathsf{BP}\cdot$ and $\mathsf{C}\cdot$, so the $\cdot$ is, in this context, not an independent piece of notation. Toda is extending the $\mathsf{BP}\cdot$ operator introduced by Schöning (but with uglier notation - $BP\mathscr{C}$ for the operator applied to class $\mathscr{C}$).

The three operators give (intuitively) the closures of classes under three different types of reductions. I'll reproduce the definition (and intuitive explanation) for $\mathsf{BP}\cdot$ for Toda's paper (p. 867):

  $L \in \mathsf{BP}\cdot\mathbf{K}$ if there exist a set $A \in \mathbf{K}$, a polynomial $p$, and a constant $\alpha > 0$ such that, for all $x\in \Sigma^{\ast}$,
  $$
\text{Prob}(\{w\in\{0,1\}^{p(|x|)}:x\#w\in A \leftrightarrow x \in L\}) \geqq \frac{1}{2}\alpha
$$

The intuitive definition is (p. 865):

  Intuitively speaking, a set is in $\mathrm{BP}\cdot\oplus \mathbf{P}$ if and only if it is reducible to a set in $\oplus\mathbf{P}$ under a polynomial-time randomized reduction with two-sided bounded error probability.


Which address bits are used for set selection/tag check in a cache?

Your result is almost correct.
The number of sets is indeed 128.
But 128=2^7
And 7 bits are required to identify a set...


Does minimum cost flow problem work for real valued edge weights/costs?

In the case of the Ford-Fulkerson algorithm, yes, it's due to complexity. When the edge weights/capacities aren't integers, things get really annoying, really fast.

If you allow all real numbers, you can end up with an instance that doesn't terminate. Normally, you augment paths until you can no longer do so. An irrational capacity value could allow the algorithm to continually find smaller and smaller augmenting paths.

Uri Zwick came up with a good example to show this:

  Consider the flow network shown on the right, with source $s$, sink
  $t$, capacities of edges $e_1$, $e_2$ and $e_3$ respectively $1$,
  $r=(\sqrt{5}-1)/2$ and $1$ and the capacity of all other edges some
  integer $M \ge 2$. The constant $r$ was chosen so, that $r^2 = 1 - r$.
  We use augmenting paths according to the following table, where $p_1 =
> \{ s, v_4, v_3, v_2, v_1, t \}$, $p_2 = \{ s, v_2, v_3, v_4, t \}$ and
  $p_3 = \{ s, v_1, v_2, v_3, t \}$.

  Note that after step 1 as well as after step 5, the residual
  capacities of edges $e_1$, $e_2$ and $e_3$ are in the form $r^n$,
  $r^{n+1}$ and $0$, respectively, for some $n \in \mathbb{N}$. This
  means that we can use augmenting paths $p_1$, $p_2$, $p_1$ and $p_3$
  infinitely many times and residual capacities of these edges will
  always be in the same form. Total flow in the network after step 5 is
  $1 + 2(r^1 + r^2)$. If we continue to use augmenting paths as above,
  the total flow converges to $\textstyle 1 + 2\sum_{i=1}^\infty r^i = 3
> + 2r$, while the maximum flow is $2M + 1$. In this case, the algorithm never terminates and the flow doesn't even converge to the maximum
  flow.

(Wikipedia)

The Stoer-Wagner algorithm will work with non-integer capacities, and so will Simplex/LP algorithms.


Question regarding Cook-Levin theorem proof

No, it would not. The reason is that the encoding of configurations might change in 3 consecutive places with a single transition. Specifically, this happens with transitions where the head moves to the left.

For example, consider the configuration $aabqcaa$, which means that the tape contains $aabcaa$ and the head is on $c$. Now, assume that we have the transition $\delta(q,c)=\{(s,d,L)\}$. So the $c$ should be replaced with $d$, the head should move left, and the state should change to $s$. Thus, the new configuration is $aasbdaa$. You can see that the change is in 3 consecutive places.

Had you only tracked changes is 2x2 windows, you should have allowed (for example) $qc$ to turn to $bd$, meaning that you allow the head to just "disappear".


Based on definition for non negative functions
$$O(f)=\{g: \exists C>0, \exists N \in \mathbb{N}, \forall n>N, g(n) \leqslant Cf(n)\}$$
I prefer to consider your question as about $O(\min(f,g))$.
Now, if from one hand $O(f) \cap O(g) \subset O(\min(f,g))$: $\phi \leqslant C_1 \cdot f$ and $\phi \leqslant C_2 \cdot g$ we obtain $\phi \leqslant C \cdot \min(f,g)$. Reverse can be show in same way, so we can be sure that
$$O(f) \cap O(g) = O(\min(f,g))$$


A closed form expression for # of inputs of a binary tree and its number of nodes

There is a known expression linking the number of input pins and the number of nodes in a binary tree. It does not use the height of the tree.

For any binary tree the number of leaves equals the number of internal nodes plus one.

We can prove this by induction. Basis. A tree with one node has two leaves. Induction step. Whenever I replace a leaf by a new node, both the number of nodes and the number of leaves increase by one (we lose a leaf, and get two new leaves in return).


CTL formula for "for every computation it is always possible to return to the initial state"

$AGF start$ is not a well-formed CTL formula, since in CTL you cannot write GF. Every temporal quantifier must be preceded by a path quantifier.

However, $AGF start$ is a formula in CTL*, so we can ask your question about CTL*:

  Is the formula $AGFstart$ equivalent to $AGEFstart$?

The answer to this question is no. The first formula says that in every path, you will visit start infinitely often, while the second one only claims that on every path, you can always find some way to get back to start.

Try constructing a system that satisfies one but not the other.

Hint: if $AGFstart$ holds, then $AGEF start$ also holds.


Echoing Raphael's comments, this is highly subjective without knowing you personally. However, here are the things I'd consider:

Many schools are flexible for your undergrad program, meaning that what you choose likely won't affect your graduate career too too much, particularly if you take a good number of classes in each subject.

Do you like calculus/real analysis, or only discrete math? It varies from school to school, but if you're not into calculus at all, probably better to stick with CS.

Likewise, do you want to learn programming? If you have no interest in learning about caching, hardware, programming language concepts, or more "applied" aspects of computer science, then Math might suit you better. Many undergraduate CS programs serve the dual purpose of preparing coders for industry and preparing future grad students. You will likely have to take non-theoretical classes at some point.

Are you more interested in creating new algorithms, or analysing discrete structures? My guess is that CS will beter prepare you for creating new algorithms and solving problems, while Math will better prepare you for detailed proofs about discrete structure.

I would reccomend at least taking a few comp-sci classes. My experience is that people with a math backgorund, but not a computer science background, aren't equipped as well to communicate about things like algorithms and pseudocode. As an example, when talking about Breadth First Search in a math Graph Theory class, the professor had to go and define what a queue was. In a CS class, data structures will be something you cover once and then can keep using later on. Likewise, the pseudocode I've encountered in such classes was full of numbered steps and GOTOs, as apposed to the clean iterative or recursive definitions from CS classes.


Hoare-Logic: Requirements for imperfect data types

No, when using Hoare logic properly, you make sure to account for integer overflow etc. and model the full semantics of the programming language.

It is possible to use Hoare logic along the lines you suggest, but the problem with that is that it invalidates all guarantees you might have hoped for.  Since the whole point of Hoare logic is to obtain guarantees, that seems rather counterproductive.

So if you are using Hoare logic for serious verification, you make sure that the Hoare triples accurately represent all elements of the language semantics, including integer overflow (if relevant).  For instance, part of the verification task might be to prove that integer overflow cannot happen; if you don't do that, then the Hoare triples need to account for that possibility.


Is Phong shading a pixel-first computational model?

I agree that it is a bit superfluous to have the "[i]f a mesh covers more pixels in screen space than it has vertices". Basically, if it doesn't then no interpolation is needed since the color of a pixel can be determined by the vertices it contains. But this is just a degenerate case of interpolation and there isn't much reason to call it out.

Your final paragraph is roughly correct, but it does imply that you need to calculate the Phong reflection model at each pixel using the interpolated normal in the Phong shading case while you don't in the Gouraud shading case. In the latter case, you are linearly interpolating colors calculated using the Phong reflection model at the vertices to produce pixel color values. In the former case, you are linearly interpolating normal vectors calculated at the vertices to produce pixel normals which you then use in the Phong reflection model per pixel.

The Phong reflection model is the "lighting calculation".


how to make a Turing machine of a cipher?

Honestly, the answer to "How do I model X using a Turing Machine is:"

Implement the algorithm using a programming langauge, probably a simple one like lambda-calculus
Translate from that language into a Turing Machine

We could tell you how to write a machine that does a Caesar cipher, but it would just be us doing the above steps for you.

Turing Machines are very un-intuitive to program in, and they're usually not used to model algorithms directly, more as a theoretical baseline of what an algorithm is. But while there are lots of proofs that model Turing Machines in general, usually you don't deal with specific machines.

If you really need to model things directly with TMs, try using a variant of them, such as RAM machines (which would probably be much easier for modelling a Caesar Cipher), and/or multi-tape TMs, then use the known translations to ordinary machines.


Complexity of solving multiple problems of the same complexity?

Yes, you can test whether $A \cap B$ is in $\textsf{NP}$ by testing $A$ and $B$ separately. Actually, you have proven that the class $\textsf{NP}$ is closed under intersection. See this lecture note (Exercise 1) for details and other cases.


What does $\alpha_r\supset\beta_r$ mean in the tolerance definition of System Z?

In elementary logic, $A \supset B$ is notation for the formula $\neg A \lor B$ (for the implication "$A$ implies $B$").  In other words, $A \supset B$ is a formula; it is true if $A$ is false or if $B$ is true, and false otherwise.  https://math.stackexchange.com/q/1106001/14578

How you could have figured this out on your own: Read the entire paper.  For instance, a useful place would be to start would be reading the examples in Section 3, where from the examples one can reverse-engineer the probable meaning of the symbol.


Efficient algorithm for 'unsumming' a set of sums

Solution

Solution has two parts. First we discover minimal set, then we prove that it can represent the power sum set. The solution is adjusted for programming implementation.

Minimal set algorithm

Find maximal element $a_{m}$ from the sum (multi)set. $P$, the potential minimal (multi)set is initially empty.
Unless there is only one group, represent $a_{m}$ in all possible ways as a pair of sums that add up to $a_{m}$, $S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$
Check that all elements from the set of sums are included.
Find maximal element $a_{s}$ from all $S_{ij}$ (meaning together) with the following property: for each $S_{ij}$, $a_{s}$ is either in $S_{ij}$, or we can find $a_{p}$ from the set of sums so that $a_{p}+a_{s}$ is in $S_{ij}$.
If it is the case that $S_{ij}$ does not contain $a_{s}$, just the sum $a_{s}+a_{p}$, remove $a_{p}+a_{s}$ from $S_{ij}$ (or just set a mark to ignore it) and insert $a_{p}$ and $a_{s}$ in $S_{ij}$ instead.
If an element is present in every $S_{ij}$ remove it from all $S_{ij}$ once (or just set a mark to ignore it and not to touch it any longer) and add it to the list of elements of potential minimal set $P$.
Repeat until all $S_{ij}$ are empty
If some of $S_{ij}$ remains non-empty and we cannot continue, try again with the maximum value from all $S_{ij}$.
Recreate the recursive steps without removals and continue with power set coverage algorithm over $P$. (Before this, you can make a safe-check that $P$ includes all elements that cannot be represented as a sum of two elements so they must be in underlying set for sure. For example, the minimal element must be in $P$.)

(10. Observe that a minimal set solution which is the goal of the algorithm cannot contain more than one repetition of the same number.)

Example:

$$\{2,3,5,7,8,10,12,13,15\}$$

Represent 15 in all possible ways as a sum of two numbers from the set of sums.

$$(13,2),(12,3),(10,5),(8,7)$$

Try to find maximal number that is in all groups or that can be represented as a sum. Obviously we can start searching for it from 8, there is no point going above it.

13 from the first group is 13=8+5 so 13 is fine, but 12 from the second group is not fine since there is no 4 to make 12=8+4 in the set of sums. Next we try with 7. But immediately 13 cannot be covered, there is no 6.

Next we try 5. 13=5+8, 12=5+7, 10=5+5, and for the last either 8=5+3 or 7=5+2 but not both. The groups are now:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 is repeating in all groups so we extract it $P=\{5\}$. We extract 5 only once from each group.

$$(8,2),(7,3),(5,5),(3,7)$$

Obviously there is no point going higher than 5 so we try 5 again. 8=5+3, 7=5+2, so all is fine

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Extract one 5 again from all groups since it is repeating. (This is not common but our case is deliberately created to display what to do in case we have repetitions.) $P=\{5,5\}$

$$(3,2),(2,3),(5),(3,2)$$

Now we try with 3 and have 5=3+2. Add it to the group.

$$(3,2),(2,3),(3,2),(3,2)$$

Now extract 3 and 2 since they are repeating everywhere and we are fine $P=\{5,5,3,2\}$ and the groups are empty.

$$(),(),(),()$$

Now, we need to recreate recursive steps without removals, this simply means doing the above without really removing the elements from $S_{ij}$ just placing them in $P$ and marking not to alter it any longer.

$$(13,2),(12,3),(10,5),(8,7)$$
$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$
$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

Power set coverage

The purpose of this part is to check if the found minimal set is able to cover the power sum set. It is possible that a found solution can cover all given sums, but that they are not power set sums. (Technically, you could simply create a power sum set from the found minimal set and check if each sum, as power set dictates, is in the initial sum set. This is all that just merged with what we already have, so nothing is wasted. You can do this part while rewinding the recursion.)

Encode all elements from the minimal set using successive powers of 2. The order is not important. Encode the same element with a new value as many times as it is repeating. Start from C=1, every next element has C=2C.

$$(2=[1],3=[2],5=[4],5=[8])$$

Replace the elements in the restored recursion list,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

with the encoding: 2 with 1, 3 with 2, 5 with 4, and another 5 with 8. Observe that each element has different encoding even though they are repeated.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

Collect all intermediate sums, at the moment we have (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

Intermediate sums $(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

Intermediate sums $(1,2,3,4,5,8,9,10,13,14,15)$

$$\{(15),(15),(15),(15)\}$$

Check that the result is $2^m-1$, where $m$ is the number of elements in the solution, in the example $m=4$
Collect missing numbers from $1$ to $2^m-1$ in the intermediate sum list

$(6,7,11,12)$

Justify their absence in the following manner: represent each number in binary form

$(6=0110_2)$
$(7=0111_2)$
$(11=1011_2)$
$(12=1010_2)$

$6$ represents the sum of 3+5 since $0110_2$ is covering second and third element from $(2=[1],3=[2],5=[4],5=[8])$. The sum of these elements, 8, is listed in the initial sum list $\{2,3,5,7,8,10,12,13,15\}$, so all is fine.

$7$ represents the sum of 2+3+5 since $0111_2$ is covering first three elements from $(2=[1],3=[2],5=[4],5=[8])$. The sum of these elements, 10, is listed in the initial sum list so all is fine.

$11$ is 2+3+5, and 10 is in the list.
$12$ is 3+5, and 8 is in the list.

If any binary representation corresponds to the sum that cannot be found, report that there is no solution.

So all is fine and $(2,3,5,5)$ is the solution. It is the minimal solution as well.

Discussion

It was necessary to provide the algorithm that is going to check if the sums cover the power set completion, which is what is hidden in the binary expansion. For example if we exclude 8 and 7 from the initial example, the first part would still provide the solution, only the second part would report missing combinations of sums.

First part of discovering the possible minimal set is $mnlog(m)$ which comes to $m\log^2(m)$: we are looking around $m$ elements $n$ times having one $\log(m)$ binary search.

The last part is done in recursion return and it does not require any special effort, we are searching over less than $m$ elements, we need binary form which is $\log{m}$ and we have one addition and search if the sum is in the list, so together it is again about $m\log^2(m)$.

If we assume that the number of elements in the power sum set corresponds to the number of partitions of the largest element in the underlying set then the complexity is around $m\log^3(m)$. Any of the two justifies the initial sorting in order to find the largest element.

Parts of the algorithm assume that we can find the pair of sums in linear time and this requires sorting.

Incorrect start

First part of the algorithm may fail, if we have started it on the wrong foot. For example $2,3,4,5,6,7,8,9,10,11,12,13,15$ has the basic solution $2,3,4,6$ which you get if you start algorithm from 6. However we can start our algorithm from 7, since there is nothing in step 4. that would say not to, and lock ourselves in, the algorithm cannot end properly. The reason is that 7 is 7=4+3 and 4 and 3 are in the solution. So locked algorithm does not always mean that there is no solution, just to try again with lower initial value. In that case, some ideas about the possible values are hidden within remaining $S_{ij}$. That is why we suggested starting from there in case of failure.

Another example, if you miss and start algorithm from 5, you would get $5,4,3,3$ but this one does not include 2.

Notice that this algorithm is not going to give a derived solutions like $2,2,3,4,4$, which we got simply by turning 6 into 4 and 2 in the solution $2,3,4,6$. There are special rules that cover these versions.

The purpose of this algorithm is to provide a solution once we have started it all correctly.

Improvements

Step 4. is the one that could be upgraded in this manner: instead of maximal we could try out every element in descending order that satisfies the given condition. We create a separate branch for each. If some branch does not give a solution, cancel it.

For example for $2,3,4,5,6,7,8,9,10,11,12,13,15$ we could try in the first round $7,6,5,4$ in separate ways since all of them are passing the first test. (There is no reason to use 2 or 3 since we know they have to be in the underlying set.) and simply continue that way all around until we collect all versions that can reach the end. This would create a full-coverage solution which would discover more than one underlying set.

Another thing, since we know that we cannot have more than one repetition if the case is minimal, we can incorporate this in our algorithm.

Overall, the condition in step 4. that a number must repeat in every group or have ability to create a sum is strong enough to get us out of direct exponential waters, which would be an algorithm of simply trying out every combination and creating the power set over each until we find a match.


How can k-means be reduced to Integer Programming

I'm not sure if you can reduce this problem to an Integer Problem, because the centers are still continuous variables. There are ways to write equivalent Mixed-Integer Problems (i.e., both integer and continuous variables) but I struggle to formulate as a Linear one because of the Euclidean norm.

First you create a boolean variable $w_{ij}$ for assignment. $w_{ij} = 1$ means observation j belongs to cluster i (and zero means it does not belong). The following constraint ensures that one sample can only belong to one group:
$$
\sum_i{w_{ij} = 1},  \forall i \in 1..k
$$

You also create non-negative continuous variables $d_{ij} \geq 0$ for distances between every observation j to every center, but use the Big M method to turn this distance zero if the observation does not belong to the cluster:
$$
d_{ij} \geq ||x_j - \mu_i|| - M(1 - w_{ij})
$$

To select a value of M you can find the distance between the two points that are furthest from each other, or any other bigger value. If M is big enough and j doesn't belong to i, we have $d_{ij} \geq L$ where L is negative, so the constraint is trivially satisfied - which means $d_{ij}$ can assume any value greater or equal to zero. If j does belong to i, then the minimum value for $d_{ij}$ is the euclidean distance between observation and cluster center.

(Note: you could use a multiplicative factor instead of Big M, like this: $
d_{ij} = ||x_j - \mu_i||w_{ij}$ - this is matematically accurate but generally doesn't work well in practice because it adds non-linearity. But since this norm is already non-linear, who knows?)

Now, if you minimize the distances (I saw in Wikipedia that the correct formulation tries to minimize the sum of distances), optimization will try to reduce every single value of $d_{ij}$, so they will clamp to the correct distances if j belongs to i, and to zero if j doesn not belong to i:

$$
\min{\sum_{ij}{d_{ij}}}
$$

I hope that helps.


Is a perfect matching's weight less than MST of a metric graph?

Given any spanning tree, here is how to construct a perfect matching with weight no larger. We consider two cases.

Case 1. The tree has some leaf $\ell$ which is an only child of its "parent" $x$. In this case we add $(\ell,x)$ to the matching, delete the vertices $\ell,x$, and continue.

Case 2. The tree has some leaf $\ell_1$ which has a sibling $\ell_2$. Let the common "parent" be $x$. The triangle inequality shows that $w(\ell_1,\ell_2) \leq w(\ell_1,x) + w(\ell_2,x)$. Accordingly, we add $(\ell_1,\ell_2)$ to the matching, delete the vertices $\ell_1,\ell_2$, and continue.

At each point in time, the remaining graph is always a tree, and the removed vertices are covered by a matching. Furthermore, the cost of the matching is always at most the cost of the edges removed from the tree. Eventually all the vertices will be exhausted, and we will be left with a perfect matching whose cost is at most the cost of the tree.


Algorithm to generate the number of tuples that satisfy the sum equals product problem.

One simple optimization you can use is as follows: since $x_1 + \cdots + x_n \leq 2n$, it follows that at most $\log_3 (2n)$ values are at least 3. You can go over all possible values for these $O(\log n)$ elements, and for each of them it should be easy to determine whether they can be completed (by adding only 1s and 2s) to a solution.

Taking this one step further, you can start adding elements to the sequence, from $x_n$ down, keeping track of the current product. If it exceeds $2n$, you can immediately halt.

You can probably optimize this much further, but this is already a good start.

Alternatively, OEIS has your sequence as A033178, and a table for $n \leq 10000$.


Good reference for average-case runtime analysis of QuickSort

Given your stats background, you will find the "indicator variable" analysis easier than the solution via recurrence equations.
It is based on computing the probability that two elements of given ranks are compared to each other.

The idea is described on the wikipedia page
and in more detail in Section 7.4 of Cormen et al. Introduction to Algorithms 3rd edition.


Generating inputs for random-testing graph algorithms?

Random graphs with small world topology

In graphs with small world topology, nodes are highly clustered yet the path length between them is small. A topology like this can make search problems very difficult, since local decisions quickly propagate globally. In other words, shortcuts can mislead heuristics. Further is has been shown that many different search problems have a small world topology.

Watts and Strogatz [1] propose a model for small world graphs. First, we start with a regular graph. Disorder is introduced into the graph by randomly rewiring each edge with probability $p$. If $p=0$, the graph is completely regular and ordered. If $p=1$, the graph is completely random and disordered. Values of $0 < p < 1$ produce graphs that are neither completely regular nor completely disordered. Graphs don't have a small world topology for $p=0$ and $p=1$.

Watts and Strogatz start from a ring lattice with $n$ nodes and $k$ nearest neighbours. A node is chosen from the lattice uniformly at random, and a rewired edge is reconnected to it. If rewiring would create a duplicate edge, it is left untouched. For large, sparse graphs they demand $n \gg k \gg \ln(n) \gg 1$, where $k \gg \ln(n)$ ensures the graph remains connected.

The model of Watts and Strogatz is somewhat popular, but does have certain drawbacks. Walsh [2] investigates the effects of randomization and restart strategies in graphs generated using the model. There's also a paper by Virtanen [3], which covers other models motivated by the need of realistic modeling of complex systems.

Random simple planar graphs

Generating random simple planar graphs on $n$ vertices uniformly at random can be done efficiently. The number of planar graphs with $n$ vertices, $g_n$, can be determined using generating functions. The value of $g_n$ for $1 \leq n \leq 9$ is $1,2,8,64,1023,32071,1823707,163947848$ and $20402420291$, respectively.  Since the numbers are too complicated, one is not expected to find a closed formula for them. Giménez and Noy [4] give a precise asymptotic estimate for the growth of $g_n$:
$$g_n \sim g \cdot n^{-7/2} \gamma^n n!,$$
where $g$ and $\gamma$ are constants determined analytically with approximate values $g \approx 0.42609$ and $\gamma \approx 27.22687$.

The proof of the result leads to a very efficient algorithm by Fusy [5]. Fusy gives an approximate size random generator and also a exact size random generator of planar graphs. The approximate size algorithm runs in linear time while the exact size algorithm runs in quadratic time. The algorithms are based on decomposition according to successive levels of connectivity: planar graph $\rightarrow$ connected $\rightarrow$ 2-connected $\rightarrow$ 3-connected $\rightarrow$ binary tree.

The algorithms then operate by translating a decomposition of a planar graph into a random generator using the framework of Boltzmann samplers by Duchon, Flajolet, Louchard and Schaeffer [6]. Given a combinatorial class, a Boltzmann sampler draws an object of size $n$ with probability to $x^n$, where $x$ is certain real parameter tuned by the user. Furthermore, the probability distribution is spread over all the objects of the class, with the property that objects of the same size have the same probability of occurring. Also, the probability distribution is uniform when restricted to a fixed size.

For a lightweight introduction, see a presentation by Fusy.

[1] D.J. Watts and S.H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440-442, 1998.

[2] Toby Walsh. Search in a small world. Proceedings of the 16th International Joint Conference on Artificial Intelligence (IJCAI-99-Vol2), pages 1172-1177, 1999.

[3] Satu Virtanen. Properties of nonuniform random graph models. Research Report A77, Helsinki University of Technology, Laboratory for Theoretical Computer Science, 2003.

[4] O. Giménez and M. Noy. Asymptotic enumeration and limit laws of planar graphs, arXiv
math.CO/0501269. An extended abstract has appeared in Discrete Mathematics and The-
oretical Computer Science AD (2005), 147-156.

[5] E. Fusy. Quadratic and linear time generation of planar graphs, Discrete Mathematics and Theoretical Computer Science AD (2005), 125-138.

[6] P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer. Boltzmann sampler for the random generation of combinatorial structures. Combinatorics, Probability and Computing, 13(4-5):577-625, 2004.


How to evaluate all possible groups of adjacent tiles in 2D array?

I suggest you use a search algorithm on the following statespace: the state is a set of adjacent tiles whose numbers sum to 7 or less; it is possible to transition from state $s$ to $s'$ if $s'$ is obtained by adding to $s$ one tile that is adjacent to some tile in $s$.  The initial state has the empty set $\emptyset$, and it can transition to any state containing a single tile.

Then, use a search algorithm, such a depth-first search or breadth-first search, to explore all states reachable from the initial state.  You can store the reachable states in a hashtable.  Whenever you discover a new reachable state, check if the numbers on its tiles sum to 7.  If they do, you have found a valid solution.

As an optimization, you can use flood-fill to find all of the groups (connected components), then apply the above algorithm separately to each group.


How to know maximum final states in a DFA?

The set of final states in the DFA that results from the subset construction is given by

$$F' = \{ S \mid S \cap F \neq \emptyset\}$$

If there are $n$ states in $Q$ and $k$ final stages in $F$,
then there are $2^k-1$ nonempty subsets of $F$ and each of these can be occur together with a subset of the $n-k$ states that are not final.


The problem of finding a longest simple cycle in a digraph is NP-hard, since the problem of finding a longest simple cycle in an undirected graph is a special case: you can consider an undirected graph to be a digraph with a symmetric edge relation.  (Longest simple cycle is NP-hard since it lets you solve Hamiltonian cycle.)


Backward data-flow: post-order or RPO on reverse CFG?

It is mostly due to the speed of convergence. To clarify, RPO visits as many predecessors possible before visiting a node so in case of forward data flow problems (like Dominator computation) this would help to converge faster. You can find more details in Engineering a compiler book (which you already know!)


You're correct that all regular languages have a LR(0) grammar. Moreover, there are LR(0) grammars which generate a non-regular language. (Exercise: Construct a LR(0) grammar for $\{ a^n b^n\,|\,n>0 \}$.)

LR-ness is a tricky concept to get a grasp on, because LR-ness is a property of the grammar, not necessarily the language. Having said that, it is known that all DCFLs can be recognised by a LR(k) parser in $O(n)$ time. It's also known that any LR(k) grammar can be mechanically transformed into an equivalent LR(1) grammar, and that there are examples for which there is no LR(0) grammar. So LR(1) is the same as DCFL/DPDA, and LR(0) is a proper subset.

So, yes, DCFL/DPDA/LR(1) sits somewhere between 3 and 4 on the Chomsky hierarchy, and LR(0) sits between that and 4. (By the way, don't forget Chomsky type 2 when you're examining hierarchies of languages and machines.)


A question about an input in a Halting Problem proof

It is an unspecified input.  Halting program proofs show that, for any given program that one claims can solve the halting problem, there exists an input for which it does not.  The proofs typically do not try to find what that input actually is, merely to prove that one must exist.


The angle between the projections of the target point, along the host surfaces, is technically called Triangulation Angle.


Delay Constrained Shortest Path in $O(D \cdot |E|)$ time

Hint: For $1 \leq d \leq D$, compute inductively the shortest distance between $s$ and any other node at delay at most $d$. Each such iteration runs in $O(|E|)$, so the total running time is $O(D|E|)$. (This assumes that the graph is connected. Otherwise you have to replace $|E|$ with $|E|+|V|$.)


Is the language $\{a^n b^m \mid 2n + 3m \le 1000 \}$ regular?

The language is finite and, as such, it is regular (all finite languages are regular).
To see that the language is finite, notice that the maximum length of each word in $L$ is upper bounded by $500$.
Indeed, if $w \in L$, and $n$ (resp. $m$) is the number of $a$s (resp. $b$s) in $w$:
$$
2|w| = 2(n + m) \le 2n+ 3m \le 1000.
$$


On the left you have a DFA that accepts the language of all strings over $\{0,1\}$ in which the XOR equals 1.

On the right you have a Mealy machine in which each output is the XOR of the two recent inputs (the first output is always zero).


Your assessment is correct.

A higher-order program takes programs as input or produces a program as output.
A first-order program takes values of base types as inputs and produces a value of base type as output.

In functional programming, functions are identified with programs, so we talk more about higher-order functions than higher-order programs.

This use of the word "higher-order" is common. For example, higher-order logics allow predicates to the arguments of other predicates.


I have never seen anyone doing error handling in the calculation of a hash function.

For a hash table to work, items must be equatable and hashable. If they are not equatable then sorry, you lost. As long as you can detect that an item is “bad” for equatability, you can just make it compare different to any item other than itself. And make it produce a hash code if constant zero or any other constant.

If you have problems calculating a hash function then you have a bigger problem that you need to solve first.


Space-unconstructable function in the proof of Savitch's theorem

Starting Point:        For inputs x, if    [there is no sequence of choices

which makes the non-deterministic machine accept x]  and

[for all positive integers S, there is a sequence of non-deterministic choices that,

when made for input x, will cause the non-deterministic machine to use more than S space]

then on input x, the deterministic machine is allowed

to run forever with no bound on its space usage.

Otherwise, such simulation would suffice for solving the halting problem:

Run the simulator until it halts or loops, then output accordingly.

With that in mind, the simulation works as follows:

S = 1
while True:
    run CAN_YIELD with space-bound S
    if that accepts then accept
    increase S by 1
    for end_state in configurations_at_which_the_nondeterministic_machine_might_have_just_used_more_than_space_(S):
        run CAN_YIELD with space-bound S and end_state
        if that accepts then break out of the for loop
    if the for loop ended without a break then REJECT


Average Time Complexity of Two Nested Loops

How to solve it in O(N)

Let's take an example sequence of numbers:

1 3 4 6 7 9

Assume we want the number of pairs (A,B) where A + B <= 12.

First, let's compare the 1st (low element) and the Nth element (high element). 9 + 1 <= 12. So that's one pair. But, as our list is sorted, 9 is the biggest number, if (9, 1) <= 12, for any other number X in the list, (X, 1) <= 12! Meaning, we can just add 6-1 (high index - low index) to the count, we don't need to test those numbers separately. Those are pairs (9,1), (7,1) ... (3,1).

Now we increase our low index to 2, we continue to 3. 9 + 3 <= 12 still, so we add 6-2 to the count. We already added (3,1) in the previous step so this is fine. This adds pairs (9,3), (7,3), (6,3), (4,3).

Again we increase the low index. 9 + 4 > 12. When this happens, we decrease the high index and add nothing to the count.

Now low index is 3 and high index is N-1. 7 + 4 <= 12. Adding 5-3... And so on.

If it is unclear why I add high index - low index every time: take for example the 7 + 4 step. I know that, because I am at high = 7, I had to skip 9 because it was too large. So I don't want to add the pair involving 9. I also know that because I am at low = 4, I already counted the pairs involving 1 and 3 in the previous steps. So I need to add pairs (7,4) and (6,4) in this step.

int count = 0;
for (int low = 0, high = list.Count - 1; high >= 1 && low != high; )
{
    if (list[high] + list[low] <= x)
    {
        count += high - low;
        low++;
    }
    else
    {
        high--;
    }
}

Regarding constants and complexity

Judging by your comment, you are confused about what is ignored and why. First, n/2 is not a constant because it depends on n. As n grows, n/2 grows, so it is clearly not constant. The constant that is ignored in n*n/2 is 1/2, and what remains is n*n.

So the complexity is N^2. The actual number of inner loop executions is N^2/2, but this is still O(N^2). The fact you brought up in your comment that the inner loop will run 50 times when 10^2 would indicate 100 times is irrelevant, here's why:

Constants are not meaningful unless they are extremely large (a 2^32 constant because your algorithm tests every 32 bit integer) or you calculate the average case cycle count on a reference architecture.

Otherwise, actual speed depends on the language used, on how many instructions each operation actually performs, prediction, caching, pipelining, etc and it is difficult to compare the constants of 2 different algorithms, just outright counting syntactic constructs is very misguided.

2X operations may run faster than X operations if what is being done, how and in which order is different. So until you dig a bit deeper and look into the things I mentioned above, counting operations in a high level language is pure wishful thinking. It is a sign of a questionable CS teaching in my opinion because it teaches a nonsense model of code execution, instead of using a valid one, but on a simple reference architecture (like Knuth does), if you insist on counting operations.

Consider these two pieces of code:

for (int j = 0; j < N - 1; j++)
    for (int i = j + 1; i < N; i++)
        r += A[i][j];

And:

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

The first example has N^2 / 2 inner loop repetitions. The second example has N^2 inner loop repetitions. The inner loop body is the same. But the second one is actually much faster on a standard computer (in fact, a smart compiler with certain settings might rewrite your code if you write the first one - so if you test this, turn off optimization)! This is because the second one has much better memory access locality - it accesses the memory locations in order, while the first one jumps around. This causes a much bigger difference in speed than running the loop twice as many times does. And this is just one of many things which affect run speed and are not immediately visible in the code.

Second example, two pieces of code:

for (int i = 0; i < N - 1; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        int a = A[i][j] * 3;
        a += 5;
        r += a;
    }
}

And:

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

Can you tell me which one has a bigger "constant"? Again, the first inner loop runs 1/2 as many times as the second one. But the first one has 3 lines of code inside the inner loop, while the second one has just one. On my machine, the first one is faster. By what factor? I have no idea (I could measure it, but I can't tell you by looking at the code). If you decide on a constant A for the first and B for the second program by looking at the code, A/B will probably not be anything like the ratio of actual execution times, making the constants meaningless.

So the 1/2 constant is meaningless. Whether a program runs twice faster than some other program depends on so many things that it is not productive to account for small constants on such a superficial level.

By the way, you have a bug in your program. The outer loop condition needs to be less than ARR_SIZE - 1 or you are setting index_j to ARR_SIZE in the last outer iteration, and as your indices are 0-based you are reading from beyond the end of your buffer.


Application of lambda function in Simply Typed Lambda Calculus

The term

(λx. x(λx. x)) (u r)

parses as

(λx. M) N
where M=(x (λx. x)) and N=(u r)

so, we can perform a $\beta$ step and obtain

M{N/x}
= (x (λx. x)){(u r) / x}
= (x{(u r) / x}   (λx. x){(u r) / x})
= ((u r)   (λx. x){(u r) / x})
= ((u r)   (λx. x))

The last term is also usually written as (u r) (λx. x) or even u r (λx. x).

A tricky part of this step is the substitution (λx. x){(u r) / x} = (λx. x). This derives from the general rule stating that for any terms A,B:

(λx. A){B / x} = (λx. A)

Indeed, the intuition here is that a substitution {B / x} only substitutes the free occurrences of x, and there are no free occurrences of x in (λx. A). This is coherent with the fact that the bound variable x in (λx. A) could be $\alpha$-converted to any fresh variable name y, obtaining (λy. A{y / x}), where x is no longer present at all (free or bound).

By comparison, this step is wrong

(λx. x(λx. x)) (u r) --> (λx. λz. z) (u r)

First, when you apply a $\beta$ step, the $\lambda x$ disappears. So, we can not have both $\lambda x$ and $\lambda z$ in the residual term. If we change the term, modifying the parentheses, we get

((λx. x)(λx. x)) (u r) --> (λz. z) (u r)

but the starting term is completely different from the original one, where
(λx. x(λx. x)) (u r) is read as ((λx. (x(λx. x))) (u r)) instead.


As @chi wrote, one good solution would be to enforce parenthesis around both applications and abstractions.

Because I want to be as close to "handwritten" lambda calculus (so I'd like to eliminate parenthesis as much as possible), I tried another approach, which eventually worked. I blocked applications from having abstractions (not parenthesised abstractions, just abstractions) on their left side, so that λx.x M will never parse to
(λx.x)M. This will force the greedy parsing of abstractions - λx.(xM), exactly as I want.

The grammar doing that might look like this:

atom: "(" expression ")" | variable
expr: atom | abstraction | application
abstraction: "λ" variable "." expr
application: atom | application (atom | abstraction)


Confused about the correctness proof of Dijkstra's algorithm

It looks like you misunderstood the nature of $d(v)$ for a vertex $v$.

$d(v)$ is designed to hold the current known shortest distance from $s$ to $v$ at each step/stage of the algorithm. That is, $d(v)$ is not a fixed value given $s$ and $v$ alone.

At the start of Dijkstra's algorithm, $d(s)$ is initialized to 0 and $d(v)$ is initialized to $\infty$ for each vertex $v\not=s$ in $G$. For example, let graph $G$ have three vertices $s, u, v$ and two edges $\{s,u\}, \{u,v\}$. The path $s,u,v$ is a shortest path from $s$ to $v$. Right right after Dijkstra's algorithm has initialized $d(u)$ to $\infty$, we have $d(u)=\infty\not=1=\delta(s,u)$. This is one of the examples you are looking for. In fact, for all graphs in which $u$ is reachable from $s$, as long as $d(u)$ has not been relaxed to $\delta(s,u)$, we will have, of course, $d(u)\not=\delta(s,u)$.

On the other hand, $d(u)=\delta(s,u)$ must hold at the time when the edge $(u, v)$ is being relaxed in Dijkstra's algorithm. That might be the reason that prompts you to raise this question. Note that as a property of the Dijkstra's algorithm, that fact is not proved yet at the point of time in that lesson.


Recursive and recursively enumerable language definition for a layman

A problem is recursive or decidable if a machine can compute the answer.

A problem is recursively enumerable or semidecidable if a machine can be convinced that the answer is positive.


What does it mean that a set of intervals is sorted by the right and left endpoints?

Yes, you are right. The intervals are of the form (left endpoint, right endpoint).
First, consider the following statement:

The intervals are indexed in order of increasing right endpoint

It means that given a set of intervals $I_{1}, \dotsc, I_{n}$, the $(\textrm{right endpoint of }I_{i})$ $\leq$ $(\textrm{right endpoint of }I_{j})$ for any $i \leq j$ and $i,j \in \{1, \dotsc,n\}$.
Similarly, you can define the sorted order based on the left endpoints. However, the sorted order based on these two criteria could be different.

Now, consider the following statement:

a set of n intervals sorted by right and left endpoints

This statement is a bit unclear since the sorted order by left endpoints could be different from the sorted order by right endpoints. However, in Section 1(Introduction) of their paper, they also mention the following statement: "set of $n$ sorted intervals (the $2n$ endpoints of the intervals are sorted). ". Therefore, the sorting by "right and left endpoint" simply means that you are sorting the set of all $2 \cdot n$ points together, i.e., the set: $\{ \ell_{1}, r_{1}, \dotsc, \ell_{n}, r_{n} \}$ is given in sorted order irrespective of point being a left or right endpoint. Furthermore, using this sorted set you can easily recover the sorting of intervals based on (right endpoint) or (left endpoint) in linear time i.e., $O(n)$. This does not change the running time of their coloring algorithm which is $O(n + k)$.


Hardness of mixed 3-SAT and 2-SAT formula

First of all, these are not subproblems but different types of problems. In one your promise me that $n/2$ of the clauses only have 2 literals, and in the other your promise me that only $\log n$ of the clauses have 3 literals. These are simply different problems.

For the general case, it is easier to think about if you let $n = n_2 + n_3$ with $n_2$ being the number of 2-literal clauses, and $n_3$ being the number of 3-literal clauses. Let $f$ be a function such that $n = f(n_3)$. If $f$ is polynomial then the question is $NP$-complete by padding. If $f$ is super-polynomial (but not exponential) then we do not know the complexity of the problem. If $f$ is exponential then your approach of brute-force shows that the problem is in $P$.

Note that for every $f$ you could choose, you have a different problem. They just look similar.


Non-deterministic Turing machine to solve graph colouring

The algorithm would be as follows:

Go through each vertex and "guess" a coloring using non-determinism. This takes time $O(V\log n)$, since this is the time it takes to write all the colors.
Check that the coloring is legal, which also takes polynomial time. If it's not legal, it rejects, and otherwise it accepts.

By definition, a non-deterministic Turing machine accepts an input if there is some accepting computation path. So the machine accepts iff some valid coloring exists.


How does the CPU know to get data from or send data to a peripheral device?

Keyboard input is handled through an interrupt – a signal sent to the CPU by the motherboard in response to your pressing a key. The CPU maintains a table of functions to call for each type of interrupt, and the operating system sets this so that control passes to it whenever a key is pressed.

The operating system maintains a buffer of pressed keys, and passes on this event to the software currently capturing the keyboard (if any), causing the call of an event handler set by the piece of software. If you run your program from a terminal, then the terminal is the relevant piece of software. It stores the keystrokes in its own buffer, which the C standard library has access to. (In terminal-based operating systems such as DOS or a Unix shell, this is handled by a system call, which is a function executed by the operating system.) The C++ iostream library, which is what your program actually uses, is a wrapper of the C standard library.


There are many ways to traverse a tree, and what is the 'successor' of 6 depends entirely on how you are traversing the tree. To illustrate this, here's the answer for some common traversal methods:

Pre-order traversal: 3.
In-order traversal: 9.
Post-order traversal: 17.
Level-order left-to-right: 18.
Lever-order right-to-left: 20.

And for completeness, you can get 7 as a successor of 6 through reverse pre-order.


I believe your proof is a bit incomplete, since you do not guarantee the shortest path to $d$ is a path which only traverses the popped nodes. You can add this part to make you proof complete :
Assume the shortest path to our vertex $d$ is the path $s \to u_1 \to u_ 2 \to \cdots \to u_l \to x \to \cdots \to  d$
Where nodes $s, u_1, u_2, \cdots, u_l$ are popped earlier, therefore their distances are correctly determined, and $x$ as the first vertex which is not popped yet. Since the edges are nonnegative, therefore $dist_x \le dist_d$ (let $dist_v$ be the actual distance of the vertex $v$). Since $x$ is the first vertex which is not popped yet, it's distance should now have been determined by relaxing $(u_l, x)$. We assumed $d$ has the smallest estimate, let it be $est_d$, so $est_d \le est_x = dist_x$, and thus $est_d \le dist_x \le dist_d \implies est_d \le dist_d$, and since estimate can never be less than actual distance, $est_d = dist_d$.
I hope my answer was helpful.


How do web browsers find out the MAC address?

So, how does the computer find out the MAC address of the server?

It doesn't. The MAC address only has validity inside a local area network (LAN), which, as the name says, is local. Unless the destination IP address resides in the same network as your machine, what it does is create a packet destined to the target IP address and forward it to its default route, usually your router. (To do so it must obtain the router's MAC address too using ARP—but this is a different matter.) Obtaining the server's MAC address is the task of the final hop which is in the same LAN as the server; a machine notices it is the final hop by checking if the destination IP lies in the same subnet as its own.

It is only when the destination IP is in the same local network as your machine that the MAC address needs to be obtained. (And this is done using ARP too.) In this case, your computer just happens to be the final hop in the route to the server.


Computer Vision algorithm to tell if camera is moving?

Use background detection algorithm, say Gaussian Mixture-based background detection (present in OpenCv) and then make some assumption - say backround takes more than 60% of image.
Then convert frames to color model which keeps luminance as separate component. Compare consecutive frames with small tolerance per color per pixel and bigger tolerance per light (to take into account shadows). If your camera is not really stationary, check by movement algorithm if frame is shifted by some distance (camera may move slightly even if it stands still), in that case compare it with shifted frame after detecting shift.

Now gather frames with some tolerance, say 95% of frames match background in at least 60% of pixels with slight shifts (it depends on distance from camera to background).
If it matches, camera was still, if not then either parameters were too big or it was moving.
Adjust parameters, done.


Euclidean algorithm - runtime in specific case

Your problem amounts to solving $2^{128} c - a^y z = 1$.  I assume you are given $a,y$ and must find $c,z$ that satisfy the equation.

I suggest you first solve
$$a^y z \equiv 1 \pmod{2^{128}}.$$
This has as solution
$$z \equiv (a^{-1})^y \pmod{2^{128}},$$
so you can find a solution for $z$ by computing the inverse of $a$ modulo $2^{128}$ (using one invocation of the Euclidean algorithm; or by a Hensel lifting method if you prefer), and raising it to the $y$th power using a fast exponentiation algorithm.  Then, compute $c = (1 + a^y z)/2^{128}$.


Redundancy elimination in the superposition calculus

a leading implementation of the superposition calculus theorem prover is E. in its description of their technology it states some basic theory & background under Proof Procedure:

E uses the DISCOUNT [DKS97] variant of the given-clause algorithm. The proof state is represented by two sets of clauses, the set P of processed clauses (initially empty) and the set U of unprocessed clauses. Clauses in U are ranked according to a heuristic evaluation function, and are processed in order. Processing will first simplify the selected clause g with all clauses in P, then simplify P with g (moving all affected clauses from P back into U), and then compute all direct consequences between g and P that can be derived using the generating inference rules (superposition, equality factoring, and equality resolution). The new clauses are simplified with respect to P and added to U, g is added to P.
This proof procedure is different from the given-clause algorithm implemented in Otter (and many provers since), which also uses U for simplification. The variant E uses was first popularized by DISCOUNT, but also is at the core of Waldmeister. Vampire and SPASS implement it in addition to their primary algorithm.

so [iiuc] the word "rewriting" may be somewhat a misnomer in the actual implementations of the theorem proving rules, because the original clauses are never "deleted" & always retained in case they can be affected or combined with later derivations. the rewriting "moves" "rewritten" clauses between $P$ and $U$ in both directions.
ie rewriting is basically like an addition of new derived (true) clauses to a list of known true clauses, and the movement between $P$ and $U$ is a strategy to find new true clauses in an efficient way (basically tracking the "frontier" in a mixed depth/breadth search, ordered by the priority function), and $P \cup U$ is the set of known true clauses.
dont know of a ref for this but think that heres the theory on all this. suppose $A \implies B$ and then $A$ was "deleted". it might still be possible to derive $B \implies A$ by other derivations and clauses. in that case it would have no effect. but if its not derivable by other routes, then in theory it could lead to changing a complete problem into an incomplete problem. dont know of a reference that shows this. it could be a doable exercise for the reader to come up with an example.
fineprint: taking stab at this question due to lack of other responses. am interested in a really authoritative answer to this question also. there is probably a better one than above but this is the best found so far after some research. suspect the question might be better addressed on say math.se, mathoverflow or TCS.se. also found it hard to come by basic descriptions of these concepts & without heavy specialized jargon.


Let us consider the following decision version of your first problem:

  Given a SAT instance, does its multilinear representation have a term of degree at most $d$?

I claim that this is the case iff the SAT instance has a satisfying assignment with at most $d$ ones.

Indeed, suppose first that $m$ is an inclusion-minimal term in the multilinear representation of the instance. Substituting 1 for the variables in $m$ and 0 for the variables outside of $m$, we get 1, that is, that the instance is satisfied. This shows that if the multilinear representation has a term of degree at most $d$, then the instance has a satisfying assignment with at most $d$ ones.

Now suppose that all terms in the multilinear representation have degree more than $d$. If we substitute any assignment with at most $d$ ones, then all monomials equal 0, and so the assignment falsifies the instance.

Therefore the decision version is equivalent to MIN-ONES-SAT, which is the following problem:

  Given a SAT instance, does it have a satisfying assignment with at most $d$ ones?

The problem is in NP (it is easy to count the number of ones in a satisfying assignment), and it is clearly NP-hard (take $d = n$). Hence the problem is NP-complete.

Using an NP oracle, we can easily find a monomial with minimal degree, equivalently, a satisfying assignment with the least ones. Just substitute a 0 in one of the variables, and see if it increases the minimum weight of a solution. If so, set this variable to 1, otherwise set it to zero, and continue to the next variable. This answers your first question.


Evolutionary algorithm - how to select the parents

As a simple method, you can use the roulette wheel selection. The idea is that every individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let $f_i$ be the fitness of the individual $i$. The probability $p_i$ of choosing $i$ as a parent for the next round is $p_i = f_i / \sum_{j=1}^{N}$, where N is the size of your population.

Here's an example in the context of TSP. For simplicity, let's say your population is only 4 individuals. Assume every individual is a tour of some length. The shorter the tour, the higher the fitness. Let the fitness values of the tours be $F = \{ 25,15,10,5 \}$. The sum of elements is 55. We divide every element $f_i$ with 55, and obtain $\{ 0.45, 0.27, 0.18, 0.09\}$. To implement the roulette wheel, you can use a weighted random generator if the language provides one (if not, just roll your own).

If you want to experiment with other genetic selection operators, look up other more complicated selection methods. To get you started on those, have a look at selection operators.


This is the decision version of MAX-3SAT, which is known to be NP-complete. In particular, if you choose $k = m$ then you get the classical NP-complete problem 3SAT.


This is quite a difficult question to answer. I would comment if I could.
The first problem is that you have not defined what you mean by a computer? Are you talking about the electrical based computers we know today or are you also including mechanical computers in your question? Here's a wiki link about the Difference Engine. The difference engine is completely mechanical but you can still technically 'program' it although it does not directly follow the paradigms of today.

Most parts of your question relate to one specific problem: How does the processing unit of a computational device work in a general way in accordance to the modern idea of software? I will give a general overview of what processor do.

A computer has three general operations: input (The input the user puts in, which includes data and what operation is wanted to be done), processing (the processor taking the input and operating on it) and output (what information is returned to the user). So what is inputted into a computer at the lowest level is some data and what is called an op-code or instruction. This is instruction is part of a collection stored in the processor (either electronically or via some other physical means) which has a defined algorithm associated with it. These instructions are considered 'basic' or low level. When something much more complicated is required to be processed, it is broken down into small parts which use these instructions to produce the desired computation in the end. Mechanical processors, specifically gearing based systems work in a similar way but accept input differently. The gears shift according to an algorithm to produce a result from a specific sequence of gear shifts initially (which is the input).

Here's a link to a Intel Lesson Series on Microprocessors

Another explanation of the CPU

From what I can gather the software you are talking about are the programs you see running on a computer. These are considered to be high level software, which are very complex when looking at this software from the perspective of a processor. Essentially the tools used to make this software and the software itself is broken down into a set of instructions for the processor to process at some point in the execution chain. With modern software there are many layers of abstraction to get from the processor to what the user sees. See this Wikipedia article about abstraction (It's the most comprehensive I could find): https://en.wikipedia.org/wiki/Abstraction_(computer_science)

Modern compilers such as gcc take human readable code and turn that into executable code which the operating system then executes. During execution the operating system will call processor instructions (which is a few abstraction levels down) in accordance to the executable code which the compiler produced.


Big-O notation for the given function whose runtime complexity grows faster than the input

If you express the runtime relative to the input value, it is O(f(n)). But often we describe the runtime relative to the input size; for k bit input it is $O(f(2^k-1))$.

Now  I guess the m-th ugly number is greater than $2^{m^{1/3}}$,  so this grows quite quickly. It would grow so fast that divisibility by 2,3 and 5 only cannot be checked in constant time.

Since others will be interested in an efficient solution: an ugly number is either 1 or a smaller ugly number multiplied by 2, 3 or 5. Algorithm:

Create a priority queue q.
Add 1 to the queue q.
For k = 1 to m
    Extract the smallest number u from the queue q.
    u is the k-th ugly number.
    Add 2u, 3u and 5u to the queue q.

This takes O(m log m) time And O(m) space. Time and space can be greatly reduced by finding a good lower and upper bound for u(m), counting the ugly numbers less than the upper bound in a double loop, and only adding numbers less than the upper bound to the priority queue.

PS You can’t classify a number as ugly in constant time.

PPS. Finding the first n ugly numbers can be done in O(n) operations except that the numbers involved might get large by merging arrays 2k, 3k and 5k in some range. Finding the n-th ugly number might be possible faster than O(n), but that’s tricky.


How to understand the notion of boolean query via Immerman's definition

Boolean queries are a special case of general queries. You can take $\tau$ to be some convenient vocabulary and choose a pair of $\tau$-structures to represent "true" and "false".

FOr a  concrete example, take $\tau$ to be the vocabulary with a single nullary relation symbol $T$. Now, associate "true" with the $\tau$-structure $\mathfrak{T}$ that has $|\mathfrak{T}|=\emptyset$ and $T^\mathfrak{T}=\{\langle\,\rangle\}$ (i.e., the nullary relation that contains the empty tuple) and "false" with the structure $\mathfrak{F}$ that has $|\mathfrak{F}|=\emptyset$ and $T^\mathfrak{F}=\emptyset$ (the nullary relation that doesn't contain the empty tuple).

Empty universes are a bit awkward, since they mean that $(\forall x\,\varphi) \rightarrow \exists x\,\varphi$ isn't a tautology. If you don't like that and/or you don't like nullary relations, make the relation $T$ unary and use a one-element universe.


The issue is that your proposed algorithm is polynomial with respect to the numerical value of the input, but not relative to the input's size. The binary encoding of $N$ requires at most $\lceil\log n\rceil$ bits, so an algorithm which takes the encoding of $N$ and preforms $\Omega(N)$ operations is actually exponential. Such algorithms are said to run in pseudo polynomial time.
Additionally, it seems that you are confusing factoring and primality testing. A possible decision version of factoring is given $(n,x)$ check whether $n$ has a factor $\le x$ (while your proposal refers to the case where only $n$ is given, and you loop to find a possible factor). While checking if a given number is prime is known to be in $P$, FACTORING is believed to lie outside of P.


Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?

No.

The class $P$ refers to the classical Turing machine model, we don't know if $BQP\subseteq P$ (we suspect that it isn't), thus this does not mean that factoring is in $P$.
We don't know how to simulate a quantum algorithm in a classical machine with only polynomial slowdown (the naive translation would result in an exponential algorithm for factoring).

Many problems in $NP$ have a quantum polynomial time solution, and also classical polynomial time solution, since $P\subseteq NP$. See our reference question for an overview and precise definitions.

The more interesting question would be if quantum computers can solve NP-hard problems efficiently, or formally, if $NP\subseteq BQP$. We suspect that this statement is false, though even $PH\subseteq BQP$ is still open. Proving $NP\not\subset BQP$ would also in turn prove that $P\neq NP$ (since $P\subseteq BQP)$.

It is also worth mentioning that factoring in not known to be NP-hard (and believed not to be) so we can still have both $NP\not\subset BQP$, and a polynomial algorithm for factoring in a quantum computer.

See these questions:

Consequences of SAT∈BQP,

Can a parallel computer simulate a quantum computer? Is BQP inside NP?,

for a discussion on the possibility of $NP\subseteq BQP$.


I don't understand what you mean by "$(A_i,B_i) = ((A_1,B_1),\ldots,(A_t,B_t))$", an obviously false statement. Perhaps you meant $(A_i,B_i) \in \{(A_1,B_1),\ldots,(A_t,B_t)\}$?

I don't quite understand your interpretation of the statement $P((A_i,B_i)) \geq p := 1/\binom{n}{2}$. Here is the correct interpretation:

  For any minimum cut $C$, the probability that Karger's algorithm outputs $C$ is at least $p := 1/\binom{n}{2}$.

This is exactly what A states.

For B, you need to give an example of a graph which satisfies $P(C) \leq 1/\binom{n}{2}$ for all cuts $C$. One such example is a cycle, an example you were probably shown in class.


Check out this link: https://stackoverflow.com/questions/40317006/pushdown-automaton-pda-for-l-anbncnn-1#= or check the answer below.

2 stack PDA to recognize the language {an bn cn dn n>=0} for this we should follow the given steps:

Use the first stack for checking an bn, this can be done by pushing a whenever you see an a and then popping a when you see a b.

Use the second stack for checking bn cn  this can be done by pushing b whenever you see a b and then popping b when you see a c.

Use the first stack for checking cn dn  this can be done by pushing c whenever you see a c and then popping c when you see a d.

Accept if both stacks are empty at the end of this process, otherwise do not accept it.

Let ^ and z be the stack symbol of stack 1 and 2 respectively, then the transition diagram of the above PDA will be as follows:


You're right – a single tree cannot be balanced, or rather, is trivially balanced. A collection of trees can, however, be balanced meaningfully: there exists a constant $M$ such that all trees in it have height at most $M\log n$, where $n$ is the number of elements in the tree.

For example, take any algorithm that uses a binary tree. We know that operations on binary tree take time $O(h)$, where $h$ is the height of the tree. Suppose now that the algorithm maintains the property that the tree is balanced; that is, the set of all trees that occur in all executions of the algorithm forms a collection of balanced trees. Then we can bound the running time of operations on the tree at a certain point in time by $O(\log n)$, where $n$ is the number of elements in the tree at that point.

In practice, we "misuse notation" by calling a single tree balanced. What we mean that the set of all "instances" of the tree are balanced. Usually what set is meant is clear from context.


Hint: How much space do you need to store a set of $10$ vertices? How much space does it take to go over all pairs of nodes in a graph?

Another hint: How much space does it take to implement the following algorithm? (I replaced 10 with 3 to make it easier to follow)

 int algorithm(int n, int G[n][n]) {
   int x, y, flag;
   int v1, v2, v3;

   for (v1 = 0; v1 < n; v1++)
     for (v2 = 0; v2 < n; v2++)
       for (v3 = 0; v3 < n; v3++) {
         flag = 0;
         for (x = 0; x < n; x++)
           for (y = 0; y < n; y++)
             if ((x != v1) && (x != v2) && (x != v3) &&
                 (y != v1) && (y != v2) && (y != v3))
               flag |= G[x][y];
         if (flag == 0)
           return 1;
       }
   return 0;
 }


Regular expression for the second symbols from the front and the back are equal

You asked two questions.  The usual rule on this site is to ask one question per post.

No, you're not allowed to use variables in regular expressions.  Regular expressions have a formal definition.  To qualify as a regular expression, you need to meet the requirements in the definition.  The definition can be found on Wikipedia or in your favorite textbook, and you'll note that it does not allow "where" or "variables".

For your first question about how to find a regular expression for a language, take a look at How to prove a language is regular?.


How to use frame based speech features for learning using a neural network classifier?

Simple neural network as a structure doesn't have invariance across time scale deformation that's why it is impractical to apply it to recognize time series. To recognize time series usually a generic communication model is used (HMM). NN could be used together with HMM to classify individual frames of speech. In such HMM-ANN configuration audio is split on frames, frame slices are passed into ANN in order to calculate phoneme probabilities and then the whole probability sequence is analyzed for a best match using dynamic search with HMM.

To train HMM-ANN you need a segmentation of speech on states. HMM-ANN system usually requires initialization from more robust HMM-GMM system thus there are no standalone HMM-ANN implementation, usually they are part of a whole speech recognition toolkit. Among popular toolkits Kaldi has implementation for HMM-ANN and even for HMM-DNN (deep neural networks).

There are several more complex types of neural networks that are intended to model sequence data. They fall into class of recursive neural networks where connections have cycles. Recursive neural network can process sequences of features of arbitrary length. RNN systems are state of the art systems these days and you can train very accurate recognition system using them, however, training is not simple. You can check RNN toolkits like CURRENNT.

A case of recursive neural networks are long-short term memory networks. They are state of the art system for speech recognition these days. You can learn more about them from the following publication:

http://arxiv.org/pdf/1303.5778.pdf


Busy-Beaver-like question for WHILE-Programs (Theoretical CS)

Use the same proof as Radó did in his paper: Assume there is a program $\Sigma$ that computes the value asked for, combine with a program that given $n$ computes $2 n$, and add $1$ to the result. Call the number of lines of the result $N$. Writing a program that computes $N$ should take at most $N$ lines (add $1$ $N$ times). Combine the above, the result is of length $2 N$ and computes a value larger than the largest it is able to compute given it's length. Contradiction, $\Sigma$ can't exist.


One of the things to remember when dealing with natural numbers (and others, but naturals are the central things here) is the encoding, and that the definitions of $P$ and $NP$ reference the length of the encoding of the input on a Turing Machine (or something closely equivalent).

So the input to integer factoring, as a decision problem, is typically two numbers $n$ and $k$ in $\mathbb{N}$, and the question is whether $n$ has a factor $d \leq k$.

So the magnitude of $n$ is $n$, but the size of its encoding may be only $O(\log n)$ (for example, in binary). This is exponentially smaller than $n$ (i.e. if we take $n' = \log_{2} n$, then $n = 2^{n'}$).

So then the $\sqrt{n}\log n$ "obvious" algorithm runs in time $2^{\frac{n'}{2}}\cdot n'$, which is exponential in the input size.


Given an analysis of an algorithm, can we get Big-O, Theta, and Omega from this analysis?

The key point is that $O(\cdot)$ and friends describe relationships between functions. Functions are purely mathematical objects and it doesn't matter what they're being used to measure. This is similar to the way that $<$ and friends describe relationships between numbers and it doesn't matter what those numbers are being used to measure.

So, in particular, it doesn't matter if your function is being used to measure the running time of some algorithm. It doesn't even matter if your function is being used to give, say, an upper bound on the running time of an algorithm. If I want to, I can give you an upper bound on a function that's a lower bound for the running time.  It's not very useful to do that but, because $O(-)$ doesn't care what the function is measuring, it makes perfect mathematical sense.  This is a bit like saying, "Jane is less than 1.75m tall and John is taller than her": I've given you an upper bound for Jane's height and Jane's height is, in turn, being used as a lower bound for John's. OK, John could have any height at all, but the mathematics makes sense.

So, all $T(n)=O(f(n))$ says is that the function $g$ is an upper bound for the function $T$, up to constant factors, for large enough inputs. It says nothing at all about any connection between the function $T$ and the real world: it doesn't say that $T$ is an upper bound for this or a lower bound for that.

With all of that out of the way, we can address the technical part of the question, but that really does just follow from the definitions, as I stated in comments.

Tou have a function $5n^3 + 100n^2 + 32n$ and you want to compare it to some other functions: $n$, $n^2$ and $n^3$. Let's call that function $T(n)$.  Apparently, the function $T$ is somehow related to the running time of some algorithm but that doesn't matter for what's about to happen.

$T(n) = O(n^3)$ because, for $n>100$, $T(n) \leq 5n^3 + n\cdot n^2 + n^2\cdot n = 7n^3$.
$T(n)\neq O(n^2)$ because, for any constant $c$, and any $n\geq c$, $5n^3 + 100n^2 + 32n > 5n^3 \geq 5cn^2 > cn^2$. Similarly, $T(n)\neq O(n)$.
$T(n) = \Omega(n^3)$ since, for any $n>0$, $T(n)> n^3$. Similarly, $T(n) = \Omega(n^2)$ and $T(n) = \Omega(n)$.
$T(n) = \Theta(n^3)$ because $T(n) = O(n^3)$ and $T(n) = \Omega(n^3)$. $T(n)\neq \Theta(n^2)$ because $T(n)\neq O(n^2)$ and $T(n)\neq \Theta(n)$ because $T(n)\neq O(n)$.


How many basic operations are there in an algorithm for the simple multiplication of two numbers of equal length?

It's hard to tell what anyone means by "comparable" in a specific context. I would take it to mean "of the same order", so something like $n^2$, maybe $100\cdot n^2$ or $0.0001\cdot n^2$, but not $n$ or $n^3$.

The final addition is doing (roughly) $n$ additions of numbers of (roughly) non-$\_$ $n$ digits, and each of those additions takes (roughly) $n$ additions of single digit numbers. So that's why you end up with (roughly) $n^2$ additions.


Is any of the assumptions hold true for the mentioned?

Regularization will always increase the MSE loss on the training set (training loss).  Intuitively, it constraints/limits the set of regression lines you can use.
However, the MSE loss on the test set can be either increase (for the same reason) or decrease (if it has helped combat overfitting and helped bias the classifier towards a simpler hypothesis, and if simpler hypotheses are more likely to be correct).


Length of longest arithmetic progression in an array

No, your approach is wrong. Consider the set of numbers $1, 3, 4, 6, 7, 8, 10$. The longest arithmetic progression(LAP) in it is $1, 4, 7, 10$, which is of even length. However, 4 and 7 are not adjacent items so your approach will not find that LAP.

Yes, your approach is correct, but to a different problem from the problem in the article you mentioned.


I'm not sure about the FPT algorithm, but I have an idea for the kernelization.

All vertices with degree > k + 1 must be in X, since otherwise you would have to pick all but one of its neighbours which would make |X| > k. So you can delete a vertex with degree > k + 1 and rerun the algorithm with the remaining graph and k = k - 1.

You can also delete any vertices with degree 0, as their deletion doesn't change the degree of any other vertices.


Prove Undecidability Without Using Rice's Theorem

So the question is, for a particular constant $k$, is there a TM which decides on input $\langle M_i \rangle$ whether there exists a string $w$ with $|w|\geq k$ such that $M_i$ halts on input $w$? Your reduction is almost correct, let me show you: Suppose that this problem is decidable, then the acceptance problem is decidable.

If the problem is decidable, then if you wanted to know whether TM $A$ accepts $w$, you could build a machine that accepts $1^kw$ only if $A$ accepts $w$, and accepts no other string, and then you would ask your question about that Turing Machine. Let me say this with more detail.

Let $BT$ (for Banach Tarski) be the Turing Machine that decides the problem you describe, and suppose we want to know whether some TM $A$ halts on input $w$ with $|w|<k$. Then we construct a TM $H_{A,w}$ as follows: $H_{A,w}$ checks whether the input is $1^kw$, i.e. $w$ padded at the beginning with $k$ ones (so $w$ is "hard-coded" into this machine). If not, it stops. If the input is $1^kw$, then it moves to the first symbol of $w$ and simulates $A$. Does $H_{A,w}$ accept any input longer than $k$? If so, then it accepts $1^kw$, because that is the only string it could possibly accept. If it accepts $1^kw$, then $A$ accepts $w$, because we were simulating $A$ on $w$. If it accepts $1^kw$, then you could ask $BT$ the question you describe about $H_{a,w}$, i.e. run $BT$ with input $H_{A,w}$. If it returns yes, then $A$ accepts $w$. If not, not.

We have now provided a reduction from the Acceptance Problem to your problem. But we know that the Acceptance Problem is undecidable! So it cannot be that your problem is decidable, because then the Acceptance Problem would be decidable. $\square$


(Although you asked about Linux, which would be off-topic, the same principles apply on most operating systems, and general principles are on-topic here.)

Threads share their code section. In many systems, even separate tasks that are executing the same program can share their code section, because the code sections are read-only, so whatever one task does won't affect the other task. I don't know how to explain this better because you don't say why you don't think it would be possible. It is possible, and it's routinely done.

Each thread has its own set of register values, including the program counter. Each thread also has its own call stack. Having its own program counter and call stack (in a way, the program counter is the top of the call stack) pretty much defines a thread. Multiple threads of the same task have program counters that each point at some place in the shared code section.

Creating a thread requires allocating memory to store its stack, and to store its register values when switching between threads. It doesn't affect the code section.


Weighted Average of Multi-Output Neural Networks

Background: The simplest method of ensembling is to take an unweighted average of the outputs of the ensembles.  In general, if you want to use a simple ensemble of neural networks for classification, there are two reasonable options:

Average the logits from each model, then apply softmax once to the averaged estimate.
Each model applies softmax to get that model's confidence score, then average the confidence scores from each model.

Both are reasonable approaches.  Both can be used with multi-class classification: you independently average all the logits or confidence scores for each class separately.  You could try both to see which works better.  Personally, I would expect option #2 might work better, but the best test is to try them.

Perrone and Cooper's method: The framework you summarize generalizes the simple method, from an unweighted average to a weighted average, where the weights are calculated in a particular way.  In principle, that theoretical framework can be used for any univariate function, i.e., any function that outputs a real number, as long as we know what the "correct" output is for each instance in the training set.

In the context of multi-class classification with neural networks, you'll only be able to use Perrone and Cooper's method with option #2, i.e., applying it to the confidence scores from the models.  You can still use it in a multi-class classification setting straightforwardly, by applying it separately to each class: to get the confidence score of the ensemble for class $c$, take a weighted average of the confidence scores of each model in the ensemble, with weights derived based on the formulas you listed.  Basically, for 10-class classification, you treat this as 10 separate univariate functions (each class is treated independently).

Caveats: That paper is from 1993.  I don't know if it is the best way to create an ensemble of neural networks.  For one thing, they appear to be using MSE error as their loss.  Early work on neural networks used MSE loss, but since then we have learned that cross-entropy loss typically works a lot better for classification tasks.  I am not sure that their method of computing the weights will "play well" with cross-entropy loss.  So, it's not clear to me that their method will perform better than a simple ensemble (unweighted average) of models trained with cross-entropy loss.  I encourage you to do some experiments before relying too heavily on their approach.


What is the link between the language defined by the Turing Machine and the algorithm that the Turing machine implements?

A Turing Machine implements an algorithm.

The algorithm will either accept, reject or loop forever on certain inputs.

If we collect all of the inputs that the Turing Machine halts and accepts on. This is the associated language recognised by the Turing Machine.