Is there an algorithm or shortcut for continually updating and summing sub-sections of arrays?

The data structures you're looking for are quad trees (for linear time queries, logarithmic time updates, quadratic space) or the more complicated 2d interval trees (for logarithmic time queries, logarithmic time updates, $O(N^2 \log N)$ space).

I suspect you are trying to solve competitive programming problem, if so please state it in your question.


Does an insecure router bypass the privacy guarantee of a VPN connection?

If you're talking about a VPN that extends to your PC/device, and similarly on the other side of the communications, and the insecure router somewhere in the path in between, then yes, an attacker should not be able to eavesdrop/snoop on the connection. The traffic would be encrypted and the attacker would not be able to understand it. This is one of the points of using the VPN in the first place. It creates a "virtual" private network over infrastructure (including routers) that may be insecure. If it doesn't even offer you this protection, then what is the point of using the VPN in the first place?
If you're talking about a site-to-site VPN, where traffic to/from your PC/device needs to get to/from the entry point of the VPN through, say, your office infrastructure, and if your office infrastructure is not otherwise secured, and this insecure router is part of that office infrastructure, then yes, an attacker may be able to eavesdrop/snoop, but even then it is not bypassing the privacy guarantee of the VPN, because the eavesdropping/snooping would be happening outside of the path that is protected by the VPN.


Why are some programming languages Turing complete but lack some abilities of other languages?

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it.

This says nothing about the language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features commonly found in modern languages.

Turing completeness tells nothing about having types, built in arrays/integers/dictionaries, input/output capabilities, network access, multithreading, dynamic allocation, ...

Just because Java does not have feature X (say, macros, higher-rank types, or dependent types), it does not suddenly stop being Turing complete.

Turing completeness and language expressiveness are two different notions.


What are the flaws in this encryption algorithm?

This is not a secure encryption scheme.  It is similar to a Hill cipher, and vulnerable to similar attacks.  For instance, it is vulnerable to known-plaintext attacks: an attacker who observes a ciphertext E and knows the corresponding message M can recover the secret key and thus decrypt all other messages that were encrypted with the same key.

The recipient will be able to decrypt if A is invertible.  If A is not invertible, then the recipient won't be able to decrypt.

See also the questions about the Hill cipher on Crypto.SE.


This asymmetry reflects a "philosophical" difference between the two algorithms.
Let us think for a moment about what each of them is trying to achieve.

DFS investigates properties related to the structure of the graph as a whole: a few examples among the many are finding strongly connected components, topological sorting, finding cycles, testing biconnectivity, testing planarity. In all those cases the output forest has a very direct and concrete meaning. For example, the usual classification of the edges as tree, forward, back or cross tells us something about what these edges "do" in the graph we are exploring.

On the other hand, BFS is normally used to determine distances w.r.t. a pre-selected node; even applications that do not explicitly mention such distances, such as testing bipartiteness, are somewhat related to the general idea of counting the steps taken in a path.

However, distances from different sources behave somewhat inconsistently: reachability sets of different nodes may be intersecting, and distances from the two original roots could be drastically different. Furthermore, when running DFS we don't care where we started searching -- as emphasized by the fact that DFS takes no input other than the graph itself -- but the output of a BFS is a function of its starting node: what would a BFS forest even mean?

Perhaps you might be able to build a structure along the lines of a depth first forest considering the minimum pairwise distances between all nodes, but it would be something very different and you wouldn't be able to get that kind of information from a single breadth first search, anyway.


How to produce a context free grammar for this language?

A common approach to figure out a context-free grammar for some simple languages is to find, by peeling off terminals, smaller and smaller languages that are nicely structured such that if you use a nonterminal to represent each smaller language, you can restore the larger languages from the smaller ones with a production rule.

$S=\{p^{3m+n}q^nr^2p^m\mid m,n\ge 0 \}$

If you peel off $p^3$ from the front and $p$ from the back $m$ times, you got language $B=\{p^nq^nr^2\mid n\ge 0 \}$. Can you see how to produce $S$ from $B$ by one production rule? In fact, that is part of what you have written.

Peeling off $r^2$ at the end, you get language $C=\{p^nq^n\mid n\ge 0 \}$. Can you get $B$ from $C$? Can you produce/recall a context-free grammar for $C$?


Does interrupt (for I/O and etc) requires support of Preemption? What is the relation between interrupts and Preemption in O.S?

For Multiprogramming you may or may not need Preemption. It depends upon the scheduling policy that is being used. For example First in First Out is non preemptive but shortest CPU burst is preemptive.

One more thing you are mixing blocking and preemption. When a process needs I/O it uses a system call. This system call results in a trap(software interrupt). Now this process is said to be blocked(waiting for I/O). Here the scheduler will definitely remove this process from running state and bring in a new process. Now please note that this whole thing does not invlove preemption.

Preemption means that the process is not blocked, yet the CPU is taken from it and given to some other process. Suppose a process is running and an interrupt comes which has no relation with this process. Now even though the process wants to run the interrupt must be served. Here we say that the process has been preempted.

Another example would be a list of processes being scheduled by shortest cpu burst algorithm. Suppose a process A having CPU burst 20 sec is running. Now suppose a new process arrives having  a CPU burst of 10 seconds. Now A must be preempted to give chance to this second process.

Preemption is actually a good thing. It allows a CPU to serve more urgent things. Yet it may also cause some problems. A process may be preempted in the middle of updating a shared variable. This may lead to race condition.

Preemption can be simply avoided by disabling interrupts. But disabling interrupts is not a good thing at all. So nowadays all kernels used preemptive approach.


Machines whose languages are their own encoding

Using the recursion theorem, for any Turing machine $T$ you can construct a Turing machine $M$ such that on input $\langle M \rangle$, $M$ executes $T$ (on the empty tape), and otherwise $M$ immediately rejects. You can use this to show that $S$ is not decidable. Using the same ideas you can explore its recognizability and co-recognizability.


Find a CFG for the language $\{ x\$y \mid x,y\in\{a,b\}^* \wedge |x| \ne |y| \}$?

Hint:
$$
L = \{ \Sigma^{m+1} \Sigma^n \$ \Sigma^n : n,m \geq 0 \} \cup \{ \Sigma^n \$ \Sigma^n \Sigma^{m+1} \},
$$
where $\Sigma = \{a,b\}$.


If you check the proof height-balancedness of red-black trees, you'll see that we essentially analyse the black-height $h_b$ of the tree which, by another important invariant, is the number of black nodes from the root to any leaf.

The property you cite then gives us the right half of

$\qquad\displaystyle h_b(T) \leq h(T) \leq 2h_b(T)$,

which allows us to carry over bounds on black-height to usual height.


What's the meaning of "Front" in "Pareto-Optimal Front"?

I think it is sort of short for "frontier" (as in boundary between one thing and another.)  The two canonical examples would be a weather front (the boundary between a cold airmass and a warm airmass) and a military front (the boundary between the areas controlled by a pair of belligerent armies).


1-to-1 cryptographically secure bit shuffling

This is known as a one-way permutation.  The "permutation" refers to the first of your two requirements; the "one-way" refers to the second of your two requirements.  There are various candidate constructions for one-way permutations, e.g., based on raising to the third power modulo an RSA modulus or other schemes.


How do you find the height of the recurrence tree $T(n,k)=T(\frac{n}{2},k)+T(n,\frac{k}{4})+nk$

Here is a recursive definition of a height of a tree $T$:

If $T$ is a leaf, then its height is 0 (some people prefer to use 1).
Otherwise, the height of $T$ is the maximum height of any of its children, plus 1.

Equivalently, the height of a tree is the maximum length of a root-to-leaf path (in edges; if you measure it in vertices, leaves should have height 1).
This makes it clear that the correct recurrence for the height is
$$
H(n,k) = \max(H(\tfrac{n}{2},k), H(n,\tfrac{k}{4})) + 1,
$$
with an appropriate base case. The solution is roughly $\max(\log_2 n, \log_4 k)$, depending on the base case.


Can I express 100 as a three-digit 9's complement number?

Nine's complement representation involves a choice of the exact range of positive and negative numbers. It is natural to let the sign depend on the MSD (most significant digit). It is even more natural to declare that numbers starting with $0,1,2,3,4$ are positive, those starting with $5,6,7,8,9$ are negative. The range of three-digit numbers is then $-500$ to $499$ rather than $-900$ to $99$, and $100$ becomes representable. I suspect that this interpretation is what Tanenbaum intended.


Completely unscientifically, the 2T (N/3) can be ignored. The 2T (2N/3) doubles whenever N is multiplied by 1.5, which starting with T(1) happens log N / log 1.5 times, so the result is about $2^{\log N / \log 1.5}$ or $N^{\log 2 / \log 1.5}$ which is about $N^{1.709}$. The n that is added is less than this, so $\Theta(N^{1.709})$ is my unscientific answer.

It just so happens that $p = \log 2 / \log 1.5 = 1.709$ also solves your equation $2 + 2^{p+1} = 3^p$. At least up to 9 decimals according to my spreadsheet.


How approximate sine using Taylor series

You use argument reduction. You know that sin (2kπ + x) = sin (x), so given an argument y, you calculate k = round (y / 2π), y' = y - 2kπ, and sin (y) = sin (y'), with y between -π and π.

You can also use sin (π + x) = - sin (x), sin (π/2 + x) = cos (x) to reduce the argument to sin (y') or cos (y') with -π/4 ≤ x ≤ π/4.

The reason why your Taylor series gives absurd results for large x is that you are adding and subtracting huge terms. Mathematically the series converges just fine, but if you have terms > $10^{20}$, these terms will have rounding errors so large that you cannot expect a good result. Reducing the argument to -π/4 ≤ x ≤ π/4 means you have much smaller terms. (Also see Pseudonym's answer how to get the argument reduction as precise as possible).

You are adding the terms of the Taylor series from the largest. Each addition has a rounding error, proportional in size to the result of the addition. So adding in this order each addition gives a large error. It is better to start with the smallest term. The two smallest terms are tiny, adding them gives a tiny rounding error.

And usually we don't actually use the Taylor series. The Taylor series has its largest error at the end of the range. You would use Chebyshev polynomials, which minimise the largest error over the whole interval. And since you don't want any errors at x = 0, you can write sin(x) = x - x * g(x) and minimise the relative error of g(x).


When would best first search be worse than breadth first search?

Best first search is different from BFS and DFS by that that it uses problem specific information to chose which node of the search tree to expand next. Best first search is informed search and DFS and BFS are uninformed searches.

In order to use informed search algorithm you need to represent the knowledge of the problem as heuristic function.

Best first search is sometimes another name for Greedy Best First Search, but it may also mean class of search algorithms, that chose to expand the most promising node based on an evaluation function(not necessary the same as the heuristics) such as Greedy Best First Search, A* and others.

If you meant Greedy Best First Search:

it is complete (finds a solution in finite graphs) like BFS
it is not optimal(to find the least cost solution) as DFS, but BFS is optimal when the cost of each arc is the same
in the worst case its time and space complexity is O($b^n$), where b is the branching factor and n is the maximal depth. For BFS time and space complexity is O($b^m$), where m is the depth of the shallowest goal.
Greedy best-first search is in most cases better than BFS- it depends on the heuristic function and the structure of the problem. If the heuristic function is not good enough it can mislead the algorithm to expand nodes that look promising, but are far from the goal. Here is one simple example

Let all arcs have the same cost, S - start node, G - goal node and h-heuristic function

Here Greedy best-first search will expand : S,B,C,D,G

And BFS will only expand : S,A,B,G


This problem cannot be solved using a (modified) Floyd-Warshall Algorithm. The underlying assumption in F.-W. is that all paths arriving at a given node can be extended along the same path to the destination. Therefore choosing the shortest path that arrives at a node is also optimal for all paths that pass through the node. By adding the fuel constraint, this assumption is broken.

More generally, problems of this form are called the Resource-Constrained Shortest Path Problems and are, in general, $\mathcal{NP}$-hard. A generic solution to this problem is to enumerate all feasible paths that lead to any node in the graph, which obviously leads to exponential time complexity. In practice, "dominance" rules are applied to prune partial paths that are clearly inferior to other partial paths; in your case such a dominance rule could be to throw away all paths arriving at a node with more refills and less fuel than another path arriving on the same node.


On complexity of the sieve, start crossing at the square of $p$

Your algorithm is wrong. The starting point should be $p$ rather than $p^2$, since in the body of the loop $k$ gets multiplied by $p$.


Should compilers automatically translate operations into shortcuts?

First compilers may (and often will depending on the optimization level) do transformations far more complex than the one you describe.  You should not be concerned about the performance implication of the way you express the increment or the division before being sure that you are using a compiler for which it matters.

But there are some other implications.  Some are just stylistic (and here my recommendation is that you just follow what is the style of your organization, if you are in position to chose the style, chose one which suit you and don't second guess yourself about it every other week).  Other are semantic.

a += 1 and a++ are equivalent only if the context allows.  In C and C++, they are both expressions, and if the result of the expression is different (a += 1 is the incremented value; a++ is the non incremented value, ++a returns the incremented value).

a/8 and a>>3 are equivalent only if the value of a is positive or null.  For negative values, C and C++ the result is not determined by the C and C++ standards but left to the implementation(*).  The most common behavior gives the same result as a/8 for exact multiple of 8.  For negative values which are not a multiple of 8, a/8 has a result truncated towards 0 (i.e. -1/8 is 0) while a>>3 is truncated towards minus infinity (i.e. -1 >> 3 is -1).  You may know that the replacement is valid for your program but that is hard to determine for the compiler which will often not do the replacement or use a more complex one.

(*) Two reasons: the standards are defined in such a way that machines with ones' complement or sign and magnitude representation for signed values is possible and what is the natural result depend on the representation; some uncommon machines have only an unsigned shift.


Simulating Turing Machine with writing only on non-input fields on read-only Turing machine

By Single-tape Turing Machines with write-protected input recognize only Regular Languages, a Turing machine that writes only on non-input fields accepts a regular language.

Any regular language can be accepted by a read-only Turing machine: just form a DFA for the regular language, then use that as the finite-state control of the Turing machine and scan the input from left to right.

Chaining those two facts together gives a full proof of the statement.


Is there an always-halting, limited model of computation accepting $R$ but not $RE$?

Yes, there are as many models of R as there are of RE! Take a model of RE, and restrict it to the total elements of the model. For example, take Turing machines that halt. Or take total recursive functions. Or take your favorite programming language (idealized to remove memory limitations) but in addition to requiring that the source code be syntactically valid, also require that the program halt on every input.

The catch is that, since the halting problem is undecidable, for any model of R, given a recursive syntax for the elements, there cannot be any algorithm to decide whether a candidate element is valid. For example, a normal programming languages has syntactic rules, and sometimes a type system, to decide whether a program is well-formed; the parser or type checker implements a decision procedure to verify that the source code is an element of the language. If you want a programming language that is a model of RE rather than R, there is no way to decide whether some source code is a valid program.

Coq only allows a subset of all recursive functions:
$\mathsf{Coq} \subsetneq \mathsf{R} \subsetneq \mathsf{RE}$. Both bounds of this inequality chain have decidable models but the middle item doesn't. Intuitively speaking, Coq only contains recursive functions whose termination can be proved by sufficiently simple arguments. While “sufficiently simple” covers just about anything mathematicians do, it is still very limited in a theoretical sense. (More precisely, Coq's theory is equivalent to I think the Peano axioms with a schema for recursion that goes up to a certain ordinal, but at that point it gets beyond my comprehension.)


How to state that a complexity bound does not depend on a given parameter size?

The usual convention is to state upfront that your big O notations are with respect to $n$, and that whenever the constant depends on some parameter $m$, then you write $O_m(\cdot)$.

If in another paper you are fine with allowing the constant to also depend on the parameter $m$, then instead you state upfront that your big O notations are with respect to $n$, and the underlying constant could depend on $m$. Then you can use Luke Matheison's suggestions that if in some case your big O doesn't depend on $m$, then you mention that in that case the underlying constant doesn't depend on $m$; but that could be more confusing than the convention in the preceding paragraph.


Logical and non logical symbols and predicates

A predicate is basically a set or a function from your universe $A$ to $\{0, 1\}$ (belongs to the set or not). More examples for that are edge relations or any kind of property you can assign to an object (e.g. male, female when $A$ is the set of all humans).

In FO you can distinguish non-logical symbols from logical symbols by looking at their interpretations via a structure. Constants, functions, and relations are assigned by this structure. Variables are not non-logical symbols because they do not change their meanings when you vary the structure you use for the interpretation of the formula. However, they also have no fixed meaning (compared to $\exists, \wedge, \neg, \ldots$), so you do not have to count them as logical symbols either.

You can probably find other sources, where variables are treated differently.


Reducing A(TM) to some decidable problem

$A(TM)$ is undecidable because a Turing machine can fail to halt on its input. $A(DFA)$ is decidable since a DFA must always halt on any input. We can always decide whether a DFA accepts some string just by running the DFA on the string and seeing whether the DFA ends up in an accepting state. Not so with a Turing machine.

It is extraordinarily unlikely that there is a valid reduction of $A(TM)$ to $A(DFA)$; that would be a bit like effectively demonstrating that triangles have actually always had 3.5 sides, not 3. If you've got such a proof you should buy as many futures in mops as you can, since there will be a lot of brain matter to clean up after all the computer scientists' and mathematicians' heads explode.

I suspect the real question may really be more about whether proofs of the form "A reduces to B. B is decidable. Therefore, A is decidable." are valid. The answer is that, as you probably expect, of course they're valid: if you ever find yourself needing to prove a problem is decidable, this is the gold standard way to do it. If you've never seen a proof like this, per se, the reasons could be either that the default assumption is that problems are decidable until proven otherwise, or because this proof method is tantamount to just designing an algorithm to solve the problem (in which case, it might not appear to be a proof of anything so much as a description of an algorithm).

To give an example: consider Bubble Sort. This can be viewed as a proof that the Sorting problem is decidable, since it reduces $Sort$ to $\{GreaterThanOrEqualTo, Swap, Loop\}$, which we know are decidable. All right, there's some hand-waving there, but you get the idea.


If you want the minimum number of single-character changes (insert, delete, substitute) that transforms the shorter string $S$ into some length-$m$ substring of $T$, then this can be done in $O(nm)$ time.

The standard algorithm for computing the edit distance between two strings runs in $O(nm)$ time.  It uses dynamic programming to build up a matrix $d[\cdot,\cdot]$ where $d[i,j]$ denotes the minimum number of single-character changes that transform $S[0\ldots i]$ to $T[0 \ldots j]$.

You can use a simple variation of this algorithm to build up a matrix $d'[\cdot,\cdot]$ where $d'[i,j]$ denotes the minimum number of single-character changes that transform $S[0\ldots i]$ to some suffix of $T[0 \ldots j]$ (i.e., to some string $T[k \ldots j]$ for some $k\le j$).  The running time remains $O(nm)$.  This is sometimes known under the name fuzzy string search.

This gives you a single distance, which represents the smallest number of single-character changes needed to transform $S$ into a length-$m$ substring of $T$.  (If you wanted to get all $n-m+1$ edit distances from $S$ to each length-$m$ substring of $T$, I don't know whether that can be done in $O(nm)$ time.)


Minimizing total distance to a point from a set of points

It's a two-dimensional facility location problem. In this case, the optimum location is the centre of gravity (also known as the barycentre or centroid) of the locations of the houses, which is easily calculated from their co-ordinates.


The regular expression on the right consists of the empty word along with all words ending in $10$. All words accepted by the regular expression on the left are of this form. It remains to show that all words accepted by the regular expression on the right are also accepted by the one on the left. This is clear for the empty word, so it remains to show the following:

  Every word ending in $10$ is accepted by $(0^*1^+0)^*$.

Indeed, every word ending in $10$ has the form
$$
0^{a_1} 1^{b_1} 0^{a_2} 1^{b_2} \cdots 0^{a_n} 1^{b_n} 0,
$$
where $b_1,a_2,b_2,\ldots,a_n,b_n \geq 1$. We can decompose this word as
$$
(0^{a_1} 1^{b_1} 0) (0^{a_2-1} 1^{b_2} 0) (0^{a_3-1} 1^{b_3} 0) \cdots (0^{a_{n-1}-1} 1^{b_n} 0) \in (0^*1^+0)^*.
$$


Deciding if a finite automata accepts strings of any length

Let $L$ the language accepted by your DFA. The question amounts to ask whether $\{ |u| \mid u \in L \} = \mathbb{N}$. To check this, just identify all letters to a single letter, say $a$, in your DFA. You will get a NFA on the alphabet $\{a\}$. It now remains to check whether this NFA accepts $a^*$.


Dynamic Program to solve an NP-complete partitioning problem

Let $\sigma(S)$ denote the sum of all the elements in $S$ and $A_i = \{a_1, \dots, a_i\}$.

Given, $i=0,\dots,n$ and $w \in \mathbb{Z}$,
define $OPT[i,w]$ as the mazimum cardinality of a subset $S \cup S' \subseteq A_i$ where $S \cap S' = \emptyset$
and $\sigma(S) - 2\sigma(S') = w$.
If no possible choice for $S$ and $S'$ exists, then let $OPT[i,w]=-\infty$.

According to the above definition:
$$
OPT[0, w] =
\begin{cases}
0 & \text{if } w=0 \\
-\infty & \text{if } w \neq 0 \\
\end{cases}
$$

For $i>0$:
$$
    OPT[i, w] = \max\{ OPT[i-1, w], 1 + OPT[i-1, w-a_i], 1+ OPT[i-1, w+2a_i] \}.
$$

The answer to your problem is true iff $OPT[n, 0] > 0$.
Each $OPT[i, w]$ can be computed in constant time (if you have already computed the values of $OPT[i-1, \cdot]$).
Moreover, there are only $O(n)$ possible choices for $i$ and $O(t)$ sensible choices for $w$, where $t = \sum_{i=1}^n a_i$.
This gives you a dynamic programming algorithm with time complexity $O(n t)$ and space complexity $O(t)$.


Counting solutions of a particular type in HORN SAT

Finding the minimal solution can be done in polynomial time (in fact, linear time), using the standard algorithm.  There is always only a single minimal solution, and the standard algorithm for testing satisfiability of a HornSAT instance will also give you the minimal solution.

Counting the number of solutions is #P-complete and thus seems to be quite hard; see Is #HORNSAT polynomial?.


$L\in NC^1$ iff there exists a sequence of poly sized formulas that decides $L$

Let the size of a circuit or formula be the number of leaves. The total number of vertices in a formula is at most twice its size.

You can prove by induction the following claim:

  If a function is computed by a fan-in 2 circuit of size $S$ and depth $D$, then it is computed by a formula of size $2^D S$.

If $L$ is in NC1 then its $n$-bit fragments have circuits of size $n^{O(1)}$ and depth $O(\log n)$. The claim shows that there are equivalent formulas of size $n^{O(1)} 2^{O(\log n)} = n^{O(1)}$.


How can I have constant time initialization for multi-dimensional arrays?

It is amortized constant time, independent of the number of elements eventually used (initialized). But going to that complexity might just not be worth the time saved (if any).

A more practical way (due to Kernighan and Pike, IIRC) is to allocate an initial number of elements for a linear array, if you run out reallocate twice the number and initialize the new elements. The amortized cost is again constant for each initialized element, with less hassle. This obviosly works only for the case in which elements are added (mostly) sequentially; but if the elements are allocated haphazardly you'll probably be better off with another type of structure, like a hash table or some sort of tree.


Tools for practicing problem solving and expression of algorithms

Problem solving is best done (in my opinion) on pencil and paper. However, some other useful tools for helping solving problems is Wolfram|Alpha. If you need to, Python is a fairly good scripting language for solving problems. Of course, this all depends on what kind of problem you are working on (for example, a geometry problem would be very difficult to solve using Python).


Do linearly dependent features in feature vectors improve the feature vector?

Though edron's thought experiment is nice, it assumes that you do not already have both of those features. If you did, then adding the third feature cannot help, because, as you say, it is linearly dependent. Assume features x1 = Year of birth, x2 = Year of death and x3 = Age = x2-x1. Then any linear predictor gives:

x1*w1 + x2*w2 + x3*w3 = x1*(w1+w3) + x2*(w2-w3)

So, nothing has been gained and we could have learned the same thing with the original features.

A better way to augment the features is to add a nonlinear function of features, such as (x2-x1)^2.


Explanation for the regular expression for the set of all string over the alphabet {0,1}

It is a Klenee operator and it means all number of $(0 + 1)(0 + 1)\cdots$ with all possible length. As $(0+1)^{10}$ means $(0+1)(0+1)\cdots(0+1)$ for ten times. Hence, All possible combinations of $0$ and $1$ are comming in $(0+1)^*$.

In the other words by the definition, it means the union of all $(0 + 1)^i$ for all $i$ from $0$ to $\infty$.


Class of languages recognised by a Forgetful Turing Machine

The class languages recognized by FTMs are the class of regular languages. A FTM can completely simulate a DFA, so each regular language can be recognized by a FTM. On the other hand, if we can prove each FTM recognizes a regular language, we have proved the assertion.

Given a FTM $F$ with the set of states $Q$, we use the Myhill–Nerode theorem to show the language it recognizes is regular. Given a string $x$, we ask the following query:

If $F$ runs on $x$, does $F$ ever leave $x$ to the right? If so, in which state is $F$ when it first moves to the first position to the right of $x$? If not, does $F$ accept $x$?

... and the following $|Q|$ queries for each state $q\in Q$:

If $F$ runs on $\underbrace{a\cdots a}_\text{the number of $a$ = $|x|$}$, but is started on the rightmost $a$ and in state $q$, does $F$ ever leave the input to the right? If so, in which state is $F$ when it first moves to first position to the right of the input? If not, does $F$ accept the input finally?

We collect the strings that give the same answers to the $|Q|+1$ queries above into the same class. Since there are $(|Q|+2)^{|Q|+1}$ possible answers to the $|Q|+1$ queries above, there are only finite many classes. Next, we are going to prove that for any strings $x,y$ in the same class, i.e., that give the same answers to the $|Q|+1$ queries, for any string $z$, $F$ accepts either both or neither of $xz$ and $yz$, which completes the proof by the Myhill–Nerode theorem.

Consider that $F$ runs respectively on $xz$ and $yz$. Note the answers to query 1 are the same for $x$ and $y$, there are two cases:

$F$ never leaves $x$ to the right on $xz$, and $F$ never leaves $y$ to the right on $yz$. In this case, $F$ runs as if the inputs are respectively $x$ and $y$. Since the answers to query 1 are the same for $x$ and $y$, $F$ accepts either both or neither of $xz$ and $yz$.
$F$ ever leaves $x$ to the right on $xz$, and $F$ ever leaves $y$ to the right on $yz$. In this case, $F$ is in the same state when it first moves to the leftmost position of $z$, so $F$ behaves the same until it returns respectively to the rightmost position of $x$ and $y$. According to the definition of FTM, the input must become $a\cdots a$ when $F$ returns, and we can apply a recursive analysis according to query 2 (you can use mathematical induction to write a strict proof). As a result, $F$ accepts either both or neither of $xz$ and $yz$.

Of course, the analysis above assumes the tape of the FTM is restricted such that the head cannot leave the input to the left. The proof is similar without this assumption.


why are WAW and WAR hazards not possible in mips architecture

in case I2 Takes less number of clock cycles than I1 for completion then can I2 access the register file going to WB phase directly in case it has nothing to do in the phase of MEM will this give rise to a hazard?

I2 reads the register R1 at its ID phase. Therefore, if implemented directly, we must have time(I2.ID)>time(I1.WB).
A more sophisticated solution would bypass the register file and take the values directly from the Memory output. In this case we need
time(I2.ID)>time(I1.MEM) and the controller becomes more involved.

If I understand your question correctly, you ask whether I2 must take 5 clocks although it doesn't use the MEM phase. The answer is YES or otherwise, it may conflict with other instructions that would try to use MEM at the same time (unless the pipeline controller stalls them when congestion appears).


In LPA*, how are predecessors/successors of a vertex defined?

If you have an undirected graph, you can convert it to a directed graph by including edges in both directions: for each undirected edge $(u,v)$, add directed edges $u \to v$ and $v \to u$.  So, if you have undirected edges, imagine applying this transformation and then running LPA* on the resulting graph.  That should make it clear what to do.

Alternatively: in an undirected graph, Pred(u) is the set of all edges incident on $u$, and so is Succ(u) (there is no distinction between them in an undirected graph).  So, yes, they can overlap.

The cost of the edges are irrelevant.


Partitioning a graph into subgraphs with overlapping nodes

I never heard of any algorithm with the constraint of having an overlap between communities larger than a given threshold (4 here).
But I suggest the following: turn your graph into its line graph, use a classical node partitioning method that gives a hierarchy of communities, and then choose a partition that fits your requirements.
More details:

the line graph is the graph in which the nodes are the links of your original graph, and these nodes are linked together if corresponding links have an extremity in common, see wikipedia on line graph.
classical community detection algorithms partition nodes into disjoint sets; doing so on the line graph will produce a partition of the edge set, with some nodes in several communities (overlap).
many classical community detection algorithms actually produce a hierarchical decomposition, often encoded as a dendrogram, i.e. a tree of communities, sub-communities, sub-sub-communities, and so on, see wikipedia on dedrograms.
a partition into communities then is a choice of a place to cut this tree, wherever it fits your needs; for instance, one may maximize a quality function and a scale parameter, see e.g. Post-Processing Hierarchical Community Structures: Quality Improvements and Multi-scale View
therefore you may choose a cut maximizing a quality function while satisfying your requirement; you may for instance start with the optimal partition regarding the quality function, and then move the cut to fit your overlap requirement.

Good luck, please keep us informed of any progress :)


MOOC recommendations for learning algorithms based on topics covered in Daspupta, Papadimitriou & Vazirani

While I cannot answer your question (MOOC for Dasgupta et al), I will make a different recommendation.
Since you seem to like the more intuitive and slightly informal approaches to learning, rather than the more formal and proof oriented approach, I think you might like the algorithms book series by Tim Roughgarden, Algorithms Illuminated.
Algorithms Illuminated is a book series of four books,

Part 1: The Basics
Part 2: Graph Algorithms and Data Structures
Part 3: Greedy Algorithms and Dynamic Programming
Part 4: Algorithms for NP-Hard Problems

The books are reasonably priced, and on the plus side, Roughgarden has made a series of videos that can be found on the aforementioned website for the books.
In addition, he has a series of lectures that have appeared as edX and coursera courses on his videos site.


History/Etymology- Map/[Hash]Map vs map()

Well, I am only a beginning MSc student in computerscience but if if followed the classes correctly the purpose of a hash is to create some memory space, let say this memory space is 10 adresses big. With a hashmap, every value you put in the hashmap gets coupled with a key. That key will first be mapped by a hashfunction to produce a unique number. That number is within the range of possible adresses in the vector. $ f: A \mapsto B $ with A the collection of possible keys and B a collection of possible adresses. Mathematically speaking this is a mapping. The value gets then saved to that adress. Now it is possible that you want to save more values than the vector allows or the hashfuntion is not completely one on one (that is every y has a unique x value it corresponds to) In that case you wil need to make the vector longer and remap every value within the vector or you reshash the value from the hashfunction with that same same value it has returned (usualy slightly edited to avoid all values being at the same place in the vector) as the parameter to find a new adress that wasn't used before. There are a number of other techniques involved and other methods but that is beside the point.
Long story short. This mapping of key values is, i believe, the reason it is called a hashmap.


Where does the interrupt handler return to?

What happens internally inside the processor could go either way depending on how the designers chose to implement it.  Either you are returning to the address that was interrupted, but it immediately gets interrupted again, in which case the next instruction that executes is the first instruction of the next handler, or you are jumping directory to the first instruction of the next handler.

In either case: the first instruction of the next handler will be executed before the instruction that was originally interrupted.  Anything else would be a priority inversion bug.


Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size).

Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset.

You could even account for duplicates by instead using a hashmap and storing the counts of each element in the first array. When checking elements in the second array for inclusion (or nonzero value), decrement the value of each key that is a match.


Compare all the Least Significant bits,
and either there are less ones or zeroes.

We continue this search only on the set where there is less of some bit, half the input at each iteration.

$$n + \frac{1}{2}n + \frac{1}{4}n + ... < 2n.$$

And we accumulate the missing bits at each step, to come to the missing number.

So the running time is $O(n)$.


Dijkstra for negative weights by adding a constant

No, this doesn't work. A path of length $\ell$ will have $\ell K$ added to its weight, so your transformation can make a path with several light edges weigh more than a path with a few medium-weight edges.  (Consider the effect of adding $2$ to each weight in a path of two weight-$1$ edges vs a path of a single weight-$3$ edge.)


Good algorithm to find all pairs of strings between 2 sets so that all words from the 1st string are all contained in the 2nd string?

I'll list two possible approaches that might be reasonably effective in practice, though their worst-case running time is no better than what you listed.

Indices

You can build up an index for each word.  Build a hash table.  For each word that appears in any clean name, the hashtable maps that word to a list of all dirty names that contain that word.  This hashtable can be built up once in a linear scan of the set of dirty names (Set2).

Then, given a clean name, iterate over the words in the clean name.  For each word, look it up in the hash table, and iterate over all the dirty names that contain that word, and check how many words it has in common with the clean name.  Keep the best match.

This can be optimized a bit.  If the clean name contains a word that occurs in many dirty names, handling that word will be slow.  So, you could find the number of times each word occurs in some dirty name (its frequency) and store this in a hash table.  Then, given a clean name, you could iterate over the words in the clean name in order of increasing frequency, keeping track of the best match you've found so far.  If you've found a match of length $\ell$, then you can stop the iteration early without iterating over $\ell-1$ highest-frequency words in the clean name without missing any valid matches.

Tries

The order of words in a name is irrelevant, so sort the words in each phrase.  For instance, 'some good product' becomes 'good product some'.  Do this to each name in each set.

Next, build a trie to represent the set of good names (Set1).  For instance, in your example the trie will be

+-- another --+-- product --+
|`-- blah --+
|`-- good --+-- product --+-- some --+
 `-- name --+-- some --+

Now, pick a dirty name.  We want to find a match for it from the trie.  I suggest you use a recursive algorithm to find all matches: to find a match for the name $w_1 \cdots w_n$ in the trie $T$, check whether there is an edge out of the root of $T$ labelled $w_1$, and if so, recursively find all matches for $w_2 \cdots w_n$ in the subtrie pointed to by that edge; also recursively find all matches for $w_2 \cdots w_n$ in $T$.  Once you have found all matches, keep the longest one.

For instance, for 'another very long product name', after sorting this becomes 'another long name product very'.  You look that up in the trie by recursively finding all matches for 'long name product very' in the subtrie +-- product --+, and by finding all matches for 'long name product very' in the main trie.

This search process can be optimized in various ways, e.g., by keeping track of the longest match found so far and stopping early if there's no way the recursive call could find a longer match based on how many words you've matched so far and how many words remain.

There's no requirement to sort by lexicographic order.  You can sort in any other order, as long as it is consistent.  For example, you could sort by the frequency of words in the entire dataset (into the least common words first), which might help reduce the number of recursive calls.


This is a one-off trick which is not part of a complete methodology. To see why the trick works, suppose that the index has the form $x10^m$. To calculate its two's complement, we first complement it to $\bar{x}01^m$, then add 1 to get $\bar{x}10^m$. ANDing the index and its two's complement, we get $0^{|x|}10^m$. Subtracting this from the index, we get $x0^{m+1}$, as needed.


Proving a certain superset the halting language is not recursive

Main idea of the proof is since $L$ is kind of superset of $L_{halt}$ we select reduction in such a way that we always deal with only that subset of $L$ which resembles $L_{halt}$.

First let us choose any encoding such that if $\langle M,w \rangle \in L_{halt}$ then $\langle M,w \rangle^R \not\in L_{halt}$. $L_{halt}$ is undecidable in every reasonable encoding so this is okay. Also this will be true for most of the encodings if we include $\langle \rangle$ also in the encoding. (Reverse will be $\rangle w^R, M^R \langle$). Also we should have $val(\langle) > val(\rangle)$. I assume that $val$ is calculated as a number with base $|\Gamma|$ where $\Gamma$ is the tape alphabet. In the question decimal base is mentioned, which means the same. We need to add extra 4 bits (= 1 decimal digit) in each cell if we do not have enough space for new symbols.

For this encoding we can have an identity reduction for valid input of the form $\langle M,w \rangle$. For invalid input not of the form $\langle M,w \rangle$ we shall reduce the input to $\langle\epsilon,\epsilon\rangle$ which does not belong to $L$. Let us call this reduction $f$. We assume that in our encoding $\langle\epsilon,\epsilon\rangle \not\in L_{halt}$.

We can now easily prove $x \in L_{halt}$ if and only if $f(x) \in L$.

($\Rightarrow$)
Let $x = \langle M,w \rangle \in L_{halt}$.
Then clearly $val(x) > val(x ^R)$.
And $\langle M,w \rangle^R \not\in L_{halt}$.
Therefore $\langle M,w \rangle \in L_3$ and hence $\langle M,w \rangle \in L$ as naturally $x \neq x^R$, Symbols $\langle,\rangle$ ensures that $x \neq x^R$.

($\Leftarrow$)

Note it $f(x) = \langle \epsilon, \epsilon \rangle$ then it does not belong to $L$. So take the other valid cases.

Let $f(x)= y =\langle M,w \rangle \in L$.
Then $\langle M,w \rangle \in L_3$, as $val(y) > val(y^R)$.
This gives us $\langle M,w \rangle \in L_{halt}$ straight away.

The idea of this proof holds even if we are given a specific encoding for $L$ as well.

1) If the encoding for $L$ is such that we do not have begin symbol $\langle$ and end symbol $\rangle$. Also assume $x_{reject}$ is a string such that $x_{reject} \not\in L$. We can easily find such a string as $L \neq \Sigma^*$. In this case the strings got by reduction will not be necessarily in $L_3$. We also assume our encoding of turing machines is such that we can find a string $\alpha$ such that $0^*\alpha$ is never a proper prefix.

To always get strings in $L_3$ we define the reduction as follows. All invalid input strings which are not of the form $\langle M,w \rangle$ are reduced to $x_{reject}$, and all valid input strings which are of the form $\langle M,w \rangle$ are reduced to $\langle M',w\alpha^R0^{|M'|+1}\rangle$. $M'$ will remove suffix $\alpha^R0^*$ and then behave as $M$.

With this reduction the proof given above can be modified slightly to prove that $L$ is undecidable.

If the encoding for $L$ is such that $\langle$ and $\rangle$ are always included and $val(\langle) < val(\rangle)$ then in the reductions given above we will always get strings from set $L_1$ and $L_2$. In this case by using $\alpha^R0^*$ suffix it is easier to get reduced strings from set $L_2$. Then it is better to reduce language $\overline{L_{halt}}$ which is also undecidable to $L$ to prove undecidability of $L$.


Question about the definition of strings that GNFA's accept

If a GNFA $A$ reconizes $\Sigma^{*}$, then $\epsilon \in \Sigma^{*}$ must be accepted. However $\epsilon \not\in \Sigma $.


Conjunctive normal form to simple elementary algebra

$\mathsf{P}$ and $\mathsf{NP}$ are classes of decision problems. Essentially, a decision problem is a function $D \subseteq \{0,1\}^\ast \times \{ 0,1 \}$ (although describing $D$ simply by giving the subset $\{ 0,1 \}^\ast \times \{ 1 \}$ is more common). A Turing machine is said to solve $D$ if, given any string $x \in \{ 0,1 \}^\ast$, it produces $D(x)$. If there is a Turing machine which does so in time bounded by a polynomial $p(|x|)$, then $D \in \mathsf{P}$. If there is a nondeterminstic Turing machine capable of doing so in polynomial time, then $D \in \mathsf{NP}$. As you can see, $\mathsf{P}$ and $\mathsf{NP}$ are unrelated to transforming representations of objects into other (equivalent) representations; they are only about saying, for some string $x$, whether $D(x) = 1$ or not.

In your case, what we can do is analyze the time complexity of each transformation.
The step CNF $\to$ AFF simply causes the formula to be longer by a constant factor and can be realized in linear time.
In AFF $\to$ EAF, the formula blows up exponentially; assuming we previously had a maximum of $t$ terms for each of the $c$ clauses, you go over every possible $t^c$ multiplication of said terms, which takes potentially exponential time.
The final EAF $\to$ SEAF step aggregates some terms and may be computed, for instance, in quadratic time (e.g., by looping over each term in the formula).
Note that these time complexities are all relative to the respective input length for each step; for instance, "linear" is supposed to mean bounded by $c |\varphi|$, where $\varphi$ is the respective formula which is given as input to the respective transformation step.

I am not aware of a name for the forms you have given. Nevertheless, considering a Boolean formula $\varphi$ as an arithmetic expression (in particular over larger fields) is usually referred to as an arithmetization of $\varphi$ and is very relevant in complexity theory; see, for instance, this and this.


Is there any neutral element for the cryptographic hash function SHA256? (or its variants)

No one knows.  It is believed to be computationally infeasible to find such a string, if one exists.  No one knows whether such a string exists.
By standard heuristics (modelling SHA256 as a random function), there is approximately a $1/e\approx 0.368$ chance that no such input exists, and approximately a $0.632$ chance that such an input exists, so if I were forced to bet, I would bet that it's more likely there exists such an input than that there doesn't, but no one knows.  Don't interpret this chance too seriously: for the specific SHA256 function, either such an input exists or it doesn't.  We don't know which is the case.
If such an input is found, it is believed that it would take about $2^{256}$ steps of computation to find it, which is completely infeasible.


Proper TSP implementation by brute force

I don't think you should build your matrix according to the integer program, but rather the distance matrix is given as input.

Label your cities in some way, for example let $1$ be Madrid, $2$ be Berlin, and $3$ be Malmo. In your matrix, the entry $(i,j)$ will contain the distance from the city $i$ to city $j$. So you'll get a $3 \times 3$ matrix with zeros on the diagonal (the distance from Madrid to Madrid is zero):

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

Notice that the matrix would be symmetric, if the distance from city $i$ to $j$ would equal the distance from $j$ to $i$.


Is there a sorting algorithm of order $n + k \log{k}$?

The short answer is no, in the worst-case comparison based algorithms, for reasons stated here.

Using a counting technique will at least take $O(n \log n)$ worst case and $O(n \log k)$ if you use a BST. Here I'll give a variant of quick-sort which also achieves $O(n \log k)$ With a slight modification and a more careful analysis of quick-sort. We will change the "pivot" of quick-sort to never put duplicate elements in separate sub-problem. The partition procedure is as follows:

partition(list A of size n):
  x = SELECT(A, n/2)

  left = list of all elements less than x
  right = list of all elements greater than x
  center = list of all elements equal to x

  return (left, center, right)

Then the overall quick-sort looks like this:

quick-sort(list A of size n):
  if all elements in A are the same:
    return A
  left, center, right = partition(A)
  quick-sort(left)
  quick-sort(right)
  return concat(left, center, right)

The important thing here is the base case, when we only have one unique element in the list, just return the list. This will ensure that we have exactly $k$ leaf nodes in our recursion tree. The recurrence at face-value is:

$$T(n) \leq \max_{i,j} \{T(n - i) + T(n - i - j)\} + O(n)$$

Obviously with some constraints on $i$ and $j$, but that's the idea. Another thing to note is that via SELECT we ensure that center contains all the median elements, this would imply that we only recurse on two sub problems of size less than $n/2$, leading us to:

$$T(n) \leq \max_{l,r} \{T(\tfrac{n}{2} - l) + T(\tfrac{n}{2} - r)\} + O(n)$$

Where $l$ would be the overlap of the median on the left side and $r$ would be overlap of median on the right side. Note that $r + l$ is the number of elements equal to the median. With this we see a clear upper bound of $O(n \log n)$. However, when we include the base cases this becomes better. If we assume that each unique element is repeated $c = n/k = n^*/k$ times (distributed evenly) then we can get the recurrence:

$$T(n) \leq \begin{cases}
1 & n \leq n^*/k\\
T(\tfrac{n}{2} - n^*/2k) + T(\tfrac{n}{2} - n^*/2k) + O(n) & \text{otherwise}
\end{cases}$$

If we do recursion tree analysis on this we can see it is $O(n \log k)$.

We could also take advantage of the fact that we do not do $n$ work at each level of recurrence, but rather at level 0 we do $O(n)$, at level 1 we do $O(n - n/k)$, at level 2 we do $O(n - 3n/k)$, at level 3 we do $O(n - 7n/k)$ and so on. Without out our assumption the analysis becomes more tricky, and we would need to do average case analysis. However, I would claim that this assumption is worst case. Intuitively if this assumption did not hold, then we have fewer repetitions for some element $x_i$, but more repetitions for some element $x_j$. Thus, making $x_j$ more likely to be in one of the center's without going too deep in the recursion tree. This would reduce the amount of work on the remaining subproblem(s)
more by removing more than $n/k$ elements from the list.


Representing partialled/curried functions in postfix notation?

The distinguishing quality of the postfix notation, a.k.a. reverse polish notation is that for its usual left-to-right evaluation strategy, just before an operator is feed from the notation, all of its operands (a.k.a as parameters or arguments) are on the top of the stack right next to each other in the expected order. Then the operator are applied to its operands immediately. The postfix notation thus has the following distinct advantages.

No operator precedence or associativity rules are needed to evaluate the notation.
Formulas can be expressed with the notation without parentheses.
The memory needed to evaluate the notation is smaller.
It is very easy to code the evaluation of the notation.

Here is one simple solution.

Instead of [[0, 2, 4, 6, 8], 1, "@add", "@map"], we will use

[[0, 2, 4, 6, 8], [1, "@add"], "@map"]

Here is how it will be processed. [0, 2, 4, 6, 8] and [1, "@add] are pushed onto the stack. When the operator "@map" is encountered, we will pop off [1, "@add"], treating it as a function object. Then with the array [0, 2, 4, 6, 8] popped off the stack, we will apply the function to the array, leaving [1, 3, 5, 7, 9] on the top of the stack.

We can simplify further.

It is quite likely that an array can be recognized conveniently and efficiently as a function object at the time when it is read as the next element of the input. For example, we should be able to detect that whether an element is an array, and if it is, check whether the last element of that array is a binary operator or not. If it is, then the array represents a function object. Otherwise, the array consists of pure data.  We can then use

[[0, 2, 4, 6, 8], [1, "@add"]]

so that we can do away with the entry "@map". Semantically, we are recognizing [1, "@add"] as a unary operator on an array without the presence of "@map". Upon applying [1, "@add"] to the array [0, 2, 4, 6, 8], we will push the result [1,3,5,7,9] to the stack. Similarly, upon processing the following JSON input,

[[0, 2, 4, 6, 8], [1, "@add"], [2, "@multiply"]],

we will leave [2, 6, 10, 14, 18] on the top of the stack.

The solution above upholds that distinguishing quality of the postfix notation. It could be extended to function objects of multiple arguments and higher order naturally and unambiguously. It can be read easily—an array of two elements whose last element is a binary operator like "@add" is a function object.

However, this solution is only one minor technique/hack to extend the primitive postfix notation. It might be helpful to study literature on postfix notation and stack-based languages for more complete and systemic usage of postfix notation. For example, check the syntax of Forth language, where new functions/words can be defined.


How does the Earley Parser store possible parses of an ambiguous sentence?

This is an example of what the graphical chart looks like when there are n tokens in the string:

$\begin{array}{}
[1,1] & [1,2] & [1,3] & \cdots & [1,n] \\
 & [2,2] & [2,3] & \cdots & [2,n] \\
 &  & [3,3] & \cdots & [3,n] \\
 &  &  & \ddots & \vdots \\
 &  &  &  &  [n,n]
\end{array}
$

Because $S$ is the root of the grammar, the two parses of $S$ will be stored in the $[1,n]$ cell of the chart. Here as you can already guess, $[i,j]$ stands for the position indices of the parses, in other word, the span.

In case of $S$, the positions span the whole string. If the positions do not span the whole string, what you have is a set of valid constituent parses in that span.

So the answer to your question is: Possible parses are stored in the same chart, they may be stored in different cells of the chart if their spans are different. If their spans are the same, they are stored in the same cell in the chart.

Btw, I think the first two rules in your grammar do not look right.
Maybe you want

S -> NP VP and VP -> V NP instead.


Time complexity of rotation array m times using temporary array

$O(n+m)$ and $O(n)$ are the same. $m$ can never be more than $n$, so $n+m\leq 2n =O(n)$.


How can there be undecidable languages in P/1?

if $L\in P/poly$ then there is a machine that decides any input $x$,  given the advice $a_{|x|}$.

However, if the advice is not given, maybe no machine can decide $L$. This is what happens in the unary case. Note that the machine doesn't know the advice and cannot compute it, i.e.,  the set of advices (for a specific $L$) may be an undecidable language.

On the other hand, if someone gives you this (possibly undecidable) set, you have more power at hands. Similarly, if you can compute this set (for a certain $L$), say get $a_n$ in $f(n)$ time, then $L$ clearly belongs to $DTIME(poly(f(n)))$.


Clarifications on primitive recursive function definition

The first equation is what you would normally write down as a mathematician if you were to define addition in terms of successor. The second equation is the same thing, except it is written in a precise manner so as to make it obvious that this indeed is a definition by primitive recursion. You have to pay close attention to details.

A function $f$ is said to be defined by primitive recursion if we can write its definition in the following form:
$$f(x_1, \ldots, x_k, 0) = u(x_1, \ldots, x_k)\\
f(x_1, \ldots, x_k, n+1) = v(x_1, \ldots, x_k, n, f(x_1, \ldots, x_k, n)$$
where $u$ is a function of $k$ arguments and $v$ is a function of $k + 2$ arguments. Furthermore, $u$ and $v$ must be known to be primitive recursive alrady.

The first equation in your question is not of this form but the second one is. Concretely:

We cannot write $f(x,0) = x$ because "$x$" is not a primitive recursive function, whereas $u_1^1$ is. Again, it does not matter that $u_1^1(x)$ happens to be the same thing as $x$ because we are doing bureaucracy, and no shortcuts are allowed.
We cannot write $f(x, y+1) = f(x,y) + 1$ because the right-hand side is not in the correct form. For it to be in correct form we need to find a suitable $g$ so that $f(x, y+1) = g(x, y, f(x, y)$. Here $g$ must take $y$ as its second argument, even if it does not need it, otherwise we are not following the correct form. With this in mind it is easy to see that $g(a, b, c) = s(u^3_2(a,b,c))$ does the job.

When you try to show that something satisfies a definition (in this case "is primitive recursive") you have to get it exactly in the correct form. Only later, when you already understand what is going on, can you start to make shortucts and wave your hands, and say "it's obvious". Your professor does not think you are at that stage (and you are not, since you asked this question).


There are no constraints on $poly(\cdot,\cdot,\cdot,\cdot)$ other than its being a polynomial, or more generally, a polynomially bounded function (that is, a function bounded by a polynomial); the difference doesn't matter in this case. Without loss of generality, you can assume that for some $A,B > 0$, $poly(x,y,z,w) = A(xyzw)^B$.

The definition is trying to model the situation that only a small number of samples is needed to learn the concept. In order to quantify "small", we need first to decide with respect to what quantities it is going to be small (in this case, $\epsilon,\delta,n,size(c)$), and second, how small is "small". In this case, we define "small" to be any function growing at most polynomially in $1/\epsilon,1/\delta,n,size(c)$. In other cases we have more stringent requirements, say we want "small" to be polynomial in $\log \frac{1}{\epsilon}, \log \frac{1}{\delta}, n, size(c)$.

A standard definition in complexity theory is that of polynomial time. We say that an algorithm for solving some problem is efficient if on an input of size $n$ it runs in time polynomial in $n$, that is, its running time $T(n)$ is bounded by some polynomial in $n$. In your terminology, we could state this as $T(n) \leq poly(n)$ for some polynomial $n$. As before, if $T(n) \leq poly(n)$ for some polynomial $poly(\cdot)$, then in fact $T(n) \leq An^B$ for some $A,B>0$, and so without loss of generality we can assume that $poly(n) = An^B$. But we don't want to decide in advance on the values of $A,B$. We are happy as long as some values of $A,B$ work.

Your case is similar, only the polynomial is allow to depend on several quantities rather than just one quantity.


determine if a turing machine halts in less than n step, in less than n step

Maybe the Turing Machine Linear Speed Up Theorem will answer your doubt (https://en.wikipedia.org/wiki/Linear_speedup_theorem)

Counter-intuitively or maybe intuitively, this states that given a Turing Machine which does something in say $n$ steps there are Turing Machines which can solve the same problem in $n/k$ steps for any constant $k$ independent of $n$. These Turing Machines would basically run $k$ steps of the original TM as $1$ step, hence having more state space, but linearly faster.

Was this your question?


Does having more bus in the computer increasing speed?

It is difficult to answer in full generality for any kind of bus but I think generally the answer is: no.

First speed is imprecise, there are two notions: latency and throughput. Increasing the width of a bus can increase throughput but it will not help latency. Second, in theory doubling the width indeed doubles the throughput, but there is much to consider than the bus itself. Indeed, the data comes from somewhere (source), is used somewhere else (destination) and will usually travel over several (internal) buses. Thus it is pointless to have a super fast external bus if your CPU and/or internal bus is slow for example. Also if the data comes, for example, from a hard drive then it cannot be read faster than some speed for mechanical reasons and increasing the bus width will not change that. The same applies to the destination: if your CPU cannot process the data fast enough, then having a large bus is also pointless.

Finally, I would like to point out that increasing the width of a bus comes with its own problems, like interference and routing.


This is only my Intuition on the problem, without any proof or explicit algorithm. This might yield an algorithm that can calculate directly the minimal path covering, or at least you might be able to use it to approximately solve the problem.

To start out, consider the simplest case: a path graph with $n$ nodes. Clearly, you will need only 2 vertices - both endpoints.
Now, lets take a look at a more complicated (and useful) graph: a cycle with $n$ nodes.
The smallest path covering must contain all nodes, since otherwise we can easily construct a path that goes through all nodes except one.
The important bit here, is that we can think of a general graph as a "combination" of such cycles and path graphs (any combination of such graphs with one or more nodes in common).
Basically, an idea behind trying to find the smallest path covering is to identify the cycles and paths. Then, start by "marking" each node at those cycles. Then using the "path graphs" try to identify which nodes you don't have to include (for example, think of two cycles connected by a path. Marking any node in one cycle is the same as marking the "endpoint" of the path graph. So the minimal path covering will mark every node that isnt in the path). Always make sure that both graphs at the endpoints of a path graph are "marked" (a graph is marked if any node in it is marked), as well as any graph connected to a node in a cycle is marked.
This is the basic idea of an algorithm to find which nodes we have to include in the minimal path covering. Try to refine this idea a bit more, and it will give a way to calculate or at least approximate the minimal path covering.


Can any problem that runs in exponential time on a deterministic RAM be run in polynomial time on a non-deterministic RAM?

We don't know, but probably not.

You shouldn't equate nondeterministic polynomial computation with deterministic exponential computation. A problem being NP-complete does mean that we probably don't know anything better than an exponential deterministic algorithm for it; however, there are a great many exponential deterministic algorithms for which we don't know any nondeterministic polynomial algorithms (e.g., anything that's EXP-complete).

There's no particular reason to assume that EXP$\,=\,$NP. In particular, exponential-time algorithms are allowed to use an exponential amount of storage, but any computation path of a polynomial-time computation can only use a polynomial amount.


Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?

So it seems you are intrigued about the relationship between the informedness of a heuristic function and its pruning power.

This is a well-known relationship established in the literature from the 80s (see for example Pearl, Judea. Heuristics, Addison-Wesley, 1984 who, by the way, has been awarded this year with the Alan Turing award).

As you already mentioned, $h_1$ is said to be more informed than $h_2$ if and only if $h_1(n)\geq h_2(n), \forall n$ in the state space. Now, provided that the heuristic function is also admissible (i.e., $h_1(n)\leq h^*(n)$ so that it never overestimates the effort to reach the goal, where $h^*(n)$ is the optimal cost to reach the goal state from node $n$), $h_2(n)$ is admissible as well since $h^* (n) \geq h_1 (n)$ by definition and $h_1(n)\geq h_2(n)$ by hipothesis, so that $h^* (n) \geq h_2 (n)$.

When considering that both heuristics are admissible, the following result applies to all $A^*$-like search algorithms: $f (n)<h^*(n)$ is a sufficient condition for expansion so that they expand all nodes meeting this property ---other algorithms expanding them as well include IDA$^*$ and RBFS. Since $f (n) = g(n) + h (n)$ where $g(n)$ is the (known) cost from the start state $s$ to node $n$ and $h(n)$ is your heuristic function (either $h_1$ or $h_2$) so that $f(n)$ is the estimated cost of the path $s-t$ when going through $n$, it immediately follows that there are, at least, as many nodes meeting this propertiy when $h_2$ is used instead of $h_1$.

The property mentioned above was already demonstrated in the original paper of the A$^*$ search algorithm and it is quite simple. In response to your comment, I posted a proof at the end of this message.

Hope this helps, this is my first post in this site,

Theorem: $f(n) < h^*(n)$ is a sufficient condition for expansion of node $n$ in A$^*$-like search algorithms provided that $h(n)$ is an admissible heuristic function.

Proof: I will proof this by induction on the number of steps of the A$^*$ search algorithm. Since the proof relies on the monotonicity of $f(n)$ I will first prove it.

$f(n) = g(n) + h(n)$ is a monotonically increasing function (when solving minimization problems). Recall the definitions of $g(n)$ and $h(n)$ provided above.

If $h(n)$ is a consistent heuristic function (i.e., a heuristic function is said to be consistent if it satisfies the triangular inequality $|h(n) - h(m)| \leq c(n,m)$ where $c(n,m)$ is the cost of the operator from $n$ to $m$), then the $f$-value of a node $m$ which is a descendant of node $n$ lies in the interval $[g(n)+c(n,m)+h(n)-c(n,m), g(n)+c(n,m)+h(n)+c(n,m)]=[g(n)+h(n), g(n)+h(n)+2c(n,m)]\geq g(n)+h(n) = f(n)$.

Incidentally, the wikipedia says: "If $h(n)$ is consistent then the value of $h(n)$ for each node along a path to goal node are non decreasing" but this is not strictly speaking true, this is just a result of the original definition provided above.

If $h(n)$ is an $inconsistent$ heuristic function (so that it that does not satisfy the aforementioned property) then $f(m)$ can be arbitrarily smaller than $f(n)$. However, since $h(n)$ is an admissible heuristic function, $max\{h(n)-c(n,m), h(m)\}$ is an admissible heuristic function for node $m$ and using it the same interval results.

Now, bearing in mind that $f(n)$ increases along a path to the goal and that $h(n)$ never overestimates the effort to reach the goal state, it is straightforward to prove the theorem by induction

Base case: the start node $s$ is introduced in the OPEN list and it is selected for expansion. Since $f(s)=g(s)+h(s)=h(s) \leq h^*(s)$ (by hypothesis of the admissibility of $h(\cdotp)$) the theorem has been proved for the base case.

Induction step: at each iteration of the A$^*$ search algorithm the first node $n$ in OPEN is selected for expansion. By induction, it is assumed that $f(n) \leq h^*(n)$. If $n = t$ (the target state), the search immediately terminates and $f(n)=g(n)+h(n)=g(n)$ is the optimal cost of the path $s-t$. Otherwise, the descendants of node $n: n_1, n_2, ... n_k$ are inserted into the OPEN list in increasing order of $f(\cdotp)$. I will now proof that the expansion of $n$ leaves the OPEN list in such a state that the first node $m$ has $f(m) \leq h^*(m)$, because it will be expanded in the next iteration this would proof the theorem by induction. Two cases might arise:

Case 1: one of the descendants of node $n, n_i$ has an $f$-value $f(n_i) = f(n)$ (recall that $f(n)$ is a monotonically increasing function). In this case, it would be ranked first (maybe along with other nodes in case of a tie), since it has the same $f$-value of its ancestor which was already first in the OPEN list.

Case 2: all the descendants of node $n, n_i, \forall i=1, \ldots k$ have $f(n_i) > f(n)$. In this case, these nodes would be arranged in OPEN after the second state in OPEN when $n$ was selected for expansion. Since $f(n_i)\leq h^* (n_i)$, but they are larger than the second best node in OPEN, node $m$ has to verify that $f(m) \leq h^*(m)$ and this concludes the proof.


Existence of suitable pseudo-random number generators to derandomize BPP to P

$P^A\neq BPP^A$ implies the inexistence of strong enough PRG's in the relativized world, not necessarily in the usual (non black box) model.

Remember that when defining a PRG, you require it to fool some adversary with bounded resources, e.g. polynomial size circuits, or probabilistic poly time Turing machines. The NW generator fools circuits of bounded size $S$ (which depends on the hardness of the problem you started your construction with), but this does not mean it can fool circuits (or Turing machines) with access to the oracle $A$.

As an example, for any PRG $G$ which fools poly time probabilistic Turing machines, let $\mathcal{O}_G$ be the oracle which tells you whether some string $s$ is a possible outcome of $G$. $G$ can no longer fool poly size Turing machines with oracle $\mathcal{O}_G$.


Are accepting states and unaccepting states distinguishable?

This depends on your definition on distinguishable. Let's assume the following definition: $A,B$ are distinguishable if for some word $x$, if the automaton starts at $A$ and reads $x$ then it accepts, while if it starts at $B$ and reads $x$ then it rejects; or vice versa.

Under than definition, any accepting state is distinguishable from any non-accepting state: just take $x$ to be the empty string.


This is not known.

$NEXP = \Sigma_{2}$ means that $NP$ and $NP^{NP}$ are different. But, $MA$ seems too weak to reach that high to catch $NP^{NP}$.


What would be the real-world implications of a constructive $P=NP$ proof?

People have given good answers assuming that $P=NP$ with some really large constant. I'm going to play the optimist and assume that we find a proof of $P=NP$ with a tractably small constant. Perhaps not likely, but I'm going to try to give some insight into what sorts of things would happen if we could efficiently solve all $NP$ problems.

Compilers: Some computer programs would get slightly faster, since compilers use graph coloring for register allocation. We would be able to allocate for large numbers of registers exactly. Existing compilers using an approximate solution (like chordal graphs) would get better output, and those using an exact solution would get faster.
Facility location: Businesses would be able to find the optimal place to place factories and supply depots to ship to their stores, when there are possibly thousands of stores and factories. Would likely not be a huge improvement over modern approximations, but would reduce costs.
Buying plane tickets: airline tickets are weird since they don't follow triangle equality. Sometimes it's cheaper to fly from A -> B -> C than directly from A -> C, something that doesn't come up when modelling distances. It would be easy to make a website that finds the absolute cheapest sequence of flights that visit some number of cities and starts and ends in your hometown.
Circuit design: electrical circuits on a chip are basically Boolean formulas. Things like minimization could be efficiently calculated, so our hardware would get a bit more efficient.
Scheduling: mad that your school put two of your exams on the same time? If $P=NP$ your school could either how many timeslots they need so no student has a conflict, or given a number of time slots, minimize the number of conflicts.

This is just a sampling of practical applications that we'd see if $NP$-completeness weren't a barrier. I'm sure I've missed many, but if the given construction had a good constant, the implications would be far reaching.


Hash function - uniformity / strong universality

Arnab provided the answer. The family $\mathcal{H} = \{h_i : i \in N\}$, where $h_i(x) = i$ for all $x \in U$, is uniform but not pairwise independent. Similarly you can come up with families which are pairwise but not $3$-wise independent, and so on.

To give a simple example, let $X,Y$ be two independent uniformly random coin tosses. Each of the possibilities $(H,H),(H,T),(T,H),(T,H)$ has the same probability. Now let $X'$ be a uniformly random coin toss, and let $Y' = X'$. Now it is not true that each of the four possibilities of $(X',Y')$ has the same probability, but each of $X',Y'$ by itself is a uniformly random coin toss.


Approximating the runtime of a practice problem

Those lines with the increments matters for the final complexity function, but do not take them in count as it will only make things messy. The function can be simplified as follow:

The outer for runs $\frac{n^2}{2}$ times, and for each of it's iterations it runs $\frac{log^3{n}}{2}$ times.

We can call the complexity function $T(n) = \frac{n^2}{2} * log^3{n}$ which leads to $O(n^2 log^3{n})$.


Tag-free garbage collection for object oriented languages

Like Häagen-Dazs ice-cream, Object Orientation comes in many flavor,
though with more nuts and bananas. Hence it is hazardous to answer
your question stated in very general terms. Specific OO languages
could have unexpected features that might raise problems with virtual
methods. I fear that trying to imagine what kind of features could make
things go wrong is a bit of a fruitless exercise. It is better to try
answering precise questions.

The basic principle of tag-free GC is that, at any time, you should be
able to inspect the memory starting from the stack, and know the
actual type of all chunks of live allocated memory (because that is
precisely what the GC will need to work). This implies also to know,
at each call point of a function/method, the current state of
activation block of the caller, whether on the stack or on the heap,
i.e. the current variables of the block and their state of
initialisation. The necessary structural information can be stored as
data descriptors to be interpreted, or as executable gc-routines for
better GC efficiency. The important point of tag-free GC is that this
information can be determined statically, in order to be stored once
with the code rather than with each instance of a type or class or of
function activation. When this information can change dynamically, as
is the case with polymorphic types, it must be possible to compute it
by tracing and compounding static type information through the dynamic
call sequence.

The fact that a method is virtual and called through a virtual table
is not in itself a problem. A caller does not need to know what it is
calling as it has no importance regarding GC for its own activation
record. The callee is supposed to know itself (the compiler sees to
it), and carry whatever information it need. The information may be
incomplete as in the case of polymorphism, and must be completed from
other type information available in the call sequence. Actually, in
a language like ML, where functions can be passed as parameters, or put
in tuples, the
caller may not know what function it is actually calling.

What matters is that the caller knows where in its code it calls the
callee, so as to determine the state of its activation block during
the call. This is
statically dependent on the call point, and can thus be inferred from
the callee return address,(in various ways depending on technical
variations used by different authors). The corresponding gc-routine
can thus be found in some way from that return address. For example,
it can be in the code right after the call, but other equivalent
techniques could be considered. So if the callee is interupted by
GC, it will be possible to do the GC for the callers activation
record. The caller does no GC work for the callee, only for its own
activation record.

What may be a problem is making sure that the callee does know the
actual type of all the values that are passed to it (as in polymorphism).
More precisely, it must be possible to find that information when the
GC occurs and must deal with the activation record of the actual
method that is access through a virtual.

I believe that being more precise on this last issue is dependent on the actual features
and classe/objects structures of the OO language, on its typing
organization.

But, as the caller does not need to know the callee, I do not see that
indirect calls can be a problem.

Another point (answering the OP's comment) is that the issue here is
not whether GC is performed from compiled code or interpreted from
descriptors, but whether it needs dynamic tag for type information.

Suggestion: to find more work on this, take your favorite search
engines (and other web resources) and look for papers
citing the Goldberg papers or its mains references. Apply the
procedure recursively, adding occasional keywords such as object
oriented or virtual.


When describing a CS paper, can it be assumed that the meaning of "tick" is known?

I've never heard those marks on the axes referred to as "ticks", though Wikipedia agrees with your usage.  Since Dave Clarke also didn't realise that's what you're talking about, I suspect that at least a sizeable minority of people aren't familiar with the term.

Why do you need to talk about the marks on the axes at all? Instead of saying "increase at tick mark '1e+02'" just say "increase at $x=100$" or whatever the variable is on that axis.  (Also, it's silly to use the notation "1e+02" for such a simple concept as 100.)  Your writing will be easier to understand if you talk about the data, rather than talking about the precise details of how you chose to represent it.


How to find all the edges shared by all diametral paths of a tree?

An $O(n^2)$ algorithm is, for each edge, remove the edge and check the diameter of the tree (the forest now). If it did not change, then the edge is not in the set.

Finding the diameter of a tree can be done in linear time See here.

However, you can apply a greedy/dp trick for an $O(n)$ algorithm. First, root the tree at some vertex $r$. Hence, each vertex, except for $r$ gets a parent. You can then from the leaves up, find the distance from a vertex to the farthest leaf in its sub-tree. Actually, we will also keep the value of the longest path when the child having the current longest path is removed. After we compute all these values in a bottom-up manner, we go again top-down, computing for each vertex, the longest path from this vertex to a leaf not in its sub-tree. Now we can on $O(deg(v))$ compute for all edges incident to $v$ if there is a path of length equal to the maximum length and not using them.

The sum of the degrees is twice as large as the number of edges in The graph hence we get a linear total running time.


The address space is the space (i.e., set) of addresses – see, e.g., Wikipedia. It's an abuse of terminology to claim that the address space is divided into pages. It isn't: it's the memory addressed by the addresses that's divided into pages.

(This confusion between addresses and the things referred to by addresses is common.  How many times have you heard people say, "I'll give you my email" when they mean "I'll give you my email address"?)


Insertion sort on small arrays in Merge Sort

The idea most probably is to chose sublist size $k$ such that merge sort likely is faster for bigger problem instances and insertion sort for smaller ones.
$\lceil s = n/k\rceil$ sub-lists may be suboptimal for merging lists of disparate size later on.
One alternative is splitting into $2^{\lfloor\log_2{n/k}\rceil}$ lists.


In the original automaton, there is no way to be in $q_1$, read one symbol, and end up in $q_1$, so in the resulting automaton, there is no loop on $q_1$.


Is there any compiler IR paradigms other than Three Address Code and Static Single Assignment (SSA) Form?

This is an extremely common approach to designing abstract machines for non-imperative languages. See, for example, the G machine or the WAM (which uses the same technique for heap allocation).


My vote is on (4) from an intuition point of view.

I just started learning this recently so take this with a grain of salt but as mentioned by D.W. the set of states can be anything you want. It is an abstract concept. However, it is natural to think of states as being valuations of the variables in the system. For example, we may think of the current state of the solar system as the current values of all variables of interest to us, such as all positions and velocities of the 8 planets in it.

Seeing it this way has another advantage. If we take the atomic propositions to be formulas of the form $x = v$ where $x$ is a variable and $v$ is a value, then the labeling function is simply the identity function: $L(S) = S$, and an atomic proposition $P$ is true in state $S$ iff $P \in S$.

The fact that the state space becomes the power set of all n-tuples of valuations of variables is not really a downside. Many of these states would simply be unreachable in any practical Kripke structure. As for your concern about states being "nested", first of all note that $S_1 \subset S_2$ means that they are actually different states. Secondly, if $S_1 \subseteq S_2$, then you have the property that anything true in $S_1$ is also true in $S_2$!

In fact, as far as I have seen, this is the interpretation used in many of the practical uses of Kripke structures that I have seen, such as in model checking in the context of formal verification.


Pumping Lemma for regular language for $a^n$ where $n$ is even fails

The pumping lemma states that:
there exists a pumping length $p$
such that for any word $w \in L$ of length $|w| \ge p$,
there exists a decomposition $w = xyz$
meeting certain properties.

There are two errors in your proof. The first is that the lemma states that there exists a pumping length $p$ but doesn't say how to compute it; you assume without proof that $6$ is a valid pumping length. This makes your proof incomplete, but it is not actually wrong: the pumping length can be anything larger than the number of nodes in the smallest finite automaton that recognizes the language, and this language can be recognized by an automaton with just two states, so any $p \ge 2$ is ok.

The fatal mistake is that you don't get the choice of the decomposition. There has to be some decomposition $w = xyz$ such that $\forall i, xy^iz \in L$. The one you picked doesn't work. In order to prove that the language isn't regular, you'd need to prove that no decomposition works. But there is a decomposition that works: take $x = aa$, $y = aa$, $z = aa$ (or any decomposition where $|y|$ is even).

You might have gotten confused with what happens when proving that a language is not regular. When proving the negation, the quantifiers are reversed: to prove that a language is not regular using the pumping lemma, we usually assume that the pumping lemma holds, so we assume the pumping lemma, and in particular we assume that for any sufficiently large word, there exists a decomposition meeting the properties, and we deduce a contradiction from that. Here, you're trying to deduce that the pumping lemma holds.


Fastest way to search a word in a word list?

Trie might help, it stores your "word list" like this:

              a
             / \
           [a]   a
           /      \
         [a]       h
                    \
                     e
                      \
                      [d]

And you can query by some operation like trie['a']['a']['h']['e'], which is just array index operation. It takes large memory but it's very efficient. The complexity of the query operation is $ O(n) $, n is the length of the queried string.


Given all maximal independent sets of a graph, find the maximum indepdent set

If an independent set is maximal, it means you cannot add any more vertices into the set. As you correctly suggest, this does not mean that the set is necessarily a maximum independent set in the graph.

You are also correct in saying that every maximum independent set is maximal, and that a graph can have several maximum independent sets.


Is there a generally accepted name for creating types that select a subset of other types?

First, the field-subset model of subtyping, while uncommon in OO languages, is common in PL theory for modelling subtyping. It's often called row subtyping.

I'm not sure if there's a general name for all the other things you've described, but I think the closest fit is refinement types, which come in many flavours.

Liquid types refine types by a boolean predicate, i.e. you can make a type which contains all values from another type satisfying a certain predicate. For example, you could have $\{ i : Int \mid 0 < i < 10 \}$ as a refinement of $Int$.
Datasort Refinements are similar to liquid types, but they constrain a type by the shape of its values. So, you can refine $(List\ Int)$ to  $ T = Cons(Int, Cons(Int, List))$, and $T$ is then the type of all $Int$-containing lists of length 2 or more.

More generally, Set-theoretic types  describe a system where can form types using intersection, union, and negation operations on existing types. Here, there is a close correspondence between subtyping and the subset-relationship between values in a type.

A general comment is that I think you need to be careful distinguishing terms from types. While you're describing sensible operations on types, the SQL example and the Prolog unification example are both operations on terms, and not on types, so they're really something different from what you're describing.

I don't think destructuring assingment has anything to do with the other things, it's just a shorthand for pattern-matching, either where there's only one case, or where we throw an error in all but one case.

Bonus Discussion

Why is this not common? Type-checking is performed often, and adding too many features makes it undecidable. The refinement-types I listed above depend on SMT-solvers for typechecking, since they require solving logical constraints.

Are there langauges that support these? The main ones I can think of are Liquid Haskell and Dependent ML. I'm not sure how often they show up in an object-oriented context, because these are areas under active research, and functional languages are generally faster to incorporate bleeding-edge ideas from PL research.


If A many-one reduces to B, does the complement of A many-one reduce to the complement of B?

Let's try an example. Here is a reduction from the set of even numbers to the set of squares: $x \mapsto 2^x$ (check it!). It is also a reduction from the set of odd numbers to the set of non-squares. Is that just by chance?

We can make the following twist: the mapping $x \mapsto 2^{x+1}$ maps the set of even numbers to the set of non-squares. Is it always the case that we can modify a reduction from $A$ to $B$ to a reduction from $A$ to $\overline{B}$?


Prove that L $\in$ NP implies L* $\in$ NP

Lets hop back to the definition of a NP language, there exists a non-deterministic Turing machine NTM that halts when given $x$.

It's not that much work to create a non-deterministic Turing machine that first splits the input string into parts non-deterministically and then simulates running NTM on each of the parts and only halts when all parts make the NTM halt.


Is reference counting GC vs. tracing GC a language property or an implementation property?

Swift guarantees that once the last reference to an object is dropped the object is deinitialized, and the deinit code is immediately run.

Obtaining this kind of guarantee through GC is not possible - at least, not without sacrifying performance. Standard GC mechanisms only ensure the deinit code is eventually run, e.g. at the next GC cycle. For precise semantics, you need a reference count somewhere.


Designing a greedy scheduling algorithm for two sets of non-mutually exclusive tasks

Nice exercise!

The usual strategy for designing greedy algorithms is to just brainstorm a bunch of different candidate strategies.  You're going to sort by some quantity; try some ideas for what that quantity might be -- maybe it is sorted by $a_i$, or by $b_i$, or by $a_i-b_i$, or something; try to come up with as many possibilities that make sense.  Then, for each candidate strategy, test whether it appears to be correct using the methods in How to prove greedy algorithm is correct.

Try that for a little while.  If you're still stuck, here's an extra hint (don't look until you've tried the above):

   See if you can figure out which of the $n$ items must come last.


How to find an arrangement of a sequence that has the lowest cost

Unfortunately, this problem is NP-hard, which can be seen by transforming it into a question on graphs.

To see this, construct the graph $G=(V,E)$ with $V=\{x_1,x_2,\ldots,x_n\}$, $(v,w)\in E$ for all $v,w\in V$ and a cost function $c:E\rightarrow \mathbb{R}$ given by $c((x_i,x_j)) : =f(x_i,x_j)$. Observe that any path visiting all vertices in $V$ exactly once corresponds uniquely to an arrangement of the original set.

To show NP-hardness, we must first formulate a decision problem corresponding to the optimization problem. One such formulation is:

  Given set $X$ of $n$ items and function $f:X\times X\rightarrow \mathbb{R}$ and an integer $T$, does there exist an arrangement such that the total cost of the arrangement is at most $T$?

By our discussion above, this problem is equivalent to

  Given the full graph $G=(V,E)$ (i.e. $E=V\times V$) of $n$ vertices and cost function $c:E\rightarrow \mathbb{R}$ and an integer $T$, does there exist an Hamiltonian path such that the total cost of the edges of this path is at most $T$?

This problem is very similar to the traveling salesman problem (TSP), but isn't quite the same, as that problem requires a Hamiltonian cycle instead of a path.

However, as @j_random_hacker mentioned, this problem is in fact equivalent to the TSP problem on a different graph, namely $G'=(V',E')$ with $V' = V\cup \{z\}$, $E'=V'\times V'$ and $c'$ such that $c'(x,y)=c(x,y)$ for all $x,y\in V$ and $c(z,x)=c(x,z)=0$ for all $x\in V'$.

Therefore, the arrangement problem is indeed equivalent to TSP, which is NP-hard.

Although NP-hardness means that there are no efficient algorithms to find an exact solution, there are still heuristics that can find decent solution in reasonable time. There are many such approaches for the TSP problem.

The fact that we know that $f$ is 'fully' non-symmetric doesn't really help, it has the same use as knowing there is no guarantee for symmetry here, which only means some approaches won't work.


Number of combinations without given pairs

Don't expect an efficient algorithm.  This is the problem of counting the number of independent sets in an undirected graph.  This problem is #P-complete [1,2], so there is unlikely to be any effective algorithm that works for arbitrary graphs.
See https://cstheory.stackexchange.com/q/10700/5038 for techniques you could use.
[1] The complexity of counting cuts and of computing the probability that a graph is connected, J. Scott Provan and Michael O. Ball, SIAM J. Computing, 12:4.
[2] The complexity of counting in sparse, regular, and planar graphs, Salil P. Vadhan, SIAM J. Computing, 31:2(398--427).


Is an inverse homomorphism always a homomorphism?

If all letters map to the same letter $\delta$, then the inverse $h^{-1}(w) = \{w\mid h(x) = w\}$ is only defined (nonempty) when $w\in\delta^*$ and would consist of all strings in $\Sigma$ that have the same length as $w$. This is not an homomorphism, as these have only one image for each input. (Except for the very special case that $|\Sigma| = |\Delta| = 1$.)

The inverse is a substitution, mapping the letter $\delta$ to the set $\Sigma$  and all other letters in $\Delta$ to the empty set.

Obviously homomorphism $h'$ maps all strings to the empty string. Thus the inverse maps the empty string to $\Sigma^*$ and all other strings to the empty set. Silly mapping, but it is a finite state transduction (finite state automaton mapping with output).

Let me explicitly answer the question from the title. No. An homomorphism is one-to-one [meaning single valued], an inverse homomorphism in many cases is one-to-many [many-valued]. (If the inverse morphism is one-to-at-most-one [injective] again it usually is not a morphism, but the morphism is called a coding, because it can be "decoded").


Is $\log{n}$ bounded from above by $n^{o(1)}$?

Consider the function $f(n) = n^{1 + \frac{1}{n}}$ which I guess you'd say is in "$O(n^{1 + o(1)})$". I'm not sure you can call it polynomial, though.

Now, compute

$\qquad \displaystyle \lim_{n \to \infty} \frac{n^{1 + \frac{1}{n}}}{n \log n} = 0$,

so you have in fact that $f \in o(n \log n)$. Therefore, functions in this funky class of yours are not even (all) asymptotic upper bounds for $n \log n$.

The difference is that $\varepsilon$ ensures a non-vanishing distance from $n^1$ whereas $o(1)$ means that functions of the form $n^{1 + o(1)}$ in fact converge towards $n \in o(n \log n)$.


Can I program a universal Turing machine to accept arbitrary input encodings?

I'm going to simplify your question, considering that a specific encoding for a universal Turing machine will necessarily include a method for the encoding of its programs. I'll also assume that the encoding of programs and their inputs are also interdependent, meaning that you can't define how the former is done well enough without defining how the latter is done, equally well, and vice-versa.

What's left for us to do then, is to be able to explore the correspondence between programs and mathematical functions. We know that there are functions that are definable, but not computable (there isn't a corresponding program). We tend to assume that every program is the encoding of a function, but that's debatable.

So, you ask (as I understand): if there is a program that computes a function under a specific encoding of the input, for a specific encoding of the machine on which it runs, if one of these encodings change, will the function still be "writable"?

The answer would have to be that, if this is not the case, then that proves the encodings are not really equivalent, i.e., the computational models they define are substantially different. In other words, with a change in encoding should come a proof of equivalence, and what that proof states is exactly that the different encodings should be able to write the same functions $-$ if writable they are.


Terms containing the Y combinator can be weakly normalizing: they can terminate for a certain order of evaluation, i.e. for a certain evaluation strategy. No term containing the Y combinator applied to another term can be strongly normalizing, i.e. no term containing Y applied to another term terminates for all evaluation strategies, since the infinite reduction chain $Y \, M \to_\beta^* M \, (Y \, M) \to_\beta^* M \, (M \, (Y \, M)) \to_\beta^* \ldots$ is possible.
There are terms $M$ such that $Y \, M$ has no normal form, i.e. such that there is no reduction strategy that reduces $Y \, M$ to a value. For example $Y (\lambda x. x) \to_\beta^* (\lambda x.x) (Y (\lambda x.x)) \to_\beta Y (\lambda x. x)$ is a recursive functions that just spins (let x = x). (The lack of another reduction chain that terminates is left as an exercise for the reader.)
Under call-by-value (only ever reducing $M \, N$ when $M$ and $N$ are values), $Y \, M$ only converges if $M$ does not use its argument, i.e. if $Y \, M$ is not “really” recursive. Under call-by-name (always reducing the outermost redex first), $Y \, M$ converges if the recursive function that it defines terminates.