How can I compute an exponential modulo a large integer?

Modular exponentiation is a well-known algorithm. It is routinely available in libraries and languages that can manipulate large integers, including Wolfram Alpha.

When making computations modulo a large number, one does not first make the whole computation in $\mathbb{N}$ and then take the remainder of the result, because for something like an exponentiation the intermediate result would be exceedingly large. Rather, the result is calculated with reductions modulo $n$ at each step. The basic idea for exponentiation is to write down the exponent $d$ in binary, and proceed one digit at a time, with the rules
$$ \begin{align*}
  x^{2d} &= (x^d)^2 & \text{adding a binary digit \(0\) to the right of \(d\)} \\
  x^{2d+1} &= (x^d)^2 \cdot x & \text{adding a binary digit \(1\) to the right of \(d\)} \\
\end{align*} $$
All computations are multiplications modulo $n$, it is never necessary to make computations involving larger numbers. There are variations on this algorithm, including iterating over the digits of $d$ from right to left instead of left to right. The number of multiplications is at most twice the number of digits of $d$.

There are techniques to perform a multiplication $a \cdot b \pmod n$ without calculating $a \cdot b$ which could be as large as $(n-1)^2$, the most popular being Montgomery reduction. Multiplication modulo $n$ can be done in time $O(\ell^2)$ where $\ell$ is the number of digits of $n$; it follows that exponentiation modulo $n$ can be done in time $O(\ell^3)$.

You can easily verify whether the value of $F(m)$ computed by Wolfram Alpha satisfies the equation $F(m)^d \equiv m \pmod n$ by running the modular exponentiation algorithm. (Easily with a computer, not by hand, for numbers of this size.)

We've seen how to compute $m^d \pmod n$ knowing $m$, $d$ and $n$. Solving the equation $F(m)^d = m \pmod n$ where $F(m)$ is the unknown is a different matter. Computing the $d$th root modulo $n$ is a hard problem in general, for which the only known methods are exponential in $\ell$ in the worst case. The problem is tractable (i.e. has polynomial complexity) when $n$ is prime, or more generally given a factorization of $n$.

It is apparent given the notations and the value of $e$ that these numbers are an example of an RSA key pair. An RSA key pair is generated starting with a number $n$ of the form $n = p \cdot q$ where $p$ and $q$ are (probable) primes and with a number $e$ satisfying certain conditions that I won't go into here; the knowledge of the factorization of $n$ makes it easy to compute a number $d$ such that $\forall m, (m^d)^e \equiv m \pmod n$ and $\forall m, (m^e)^d \equiv m \pmod n$. (If the factorization of $n$ was not known, then finding $d$ given $n$ and $e$ or equivalently finding $e$ given $n$ and $d$ would be a hard problem: it would be literally breaking the RSA cryptosystem.)

Given this supplementary knowledge, the $d$th root of $m$ modulo $n$ can be computed with a tractable operation: exponentiation. The solution $F(m)$ is $m^e \pmod n$.

The Python programming environment provides a convenient way of making calculations on large integers.

% python
Python 2.7.3 (default, Mar 13 2014, 11:03:55)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> m=112951412120151619251851615182016118201
>>> n=145906768007583323230186939349070635292401872375357164399581871019873438799005358938369571402670149802121818086292467422828157022922076746906543401224889672472407926969987100581290103199317858753663710862357656510507883714297115637342788911463535102712032765166518411726859837988672111837205085526346618740053
>>> d=89489425009274444368228545921773093919669586065884257445497854456487674839629818390934941973262879616797970608917283679875499331574161113854088813275488110588247193077582527278437906504015680623423550067240042466665654232383502922215493623289472138866445818789127946123407807725702626644091036502372545139713
>>> e=65537
>>> pow(m,e,n)
141781201173392662619041096248902274075236734827860244551641082388116267289894721928886528279400665340976615948053755946789302972467196231829204061441862114262117040263042768989461016645192295451421289297123899909172989906731037919155114663997141846344255396618911673987467404521083471325973763420396488985050L
>>> pow(pow(m,e,n),d,n)
112951412120151619251851615182016118201L
>>> pow(pow(m,e,n),d,n) == m
True


Hint: Find first the element of rank $r_{(k+1)/2}$, and split the list accordingly into two parts $S_1,S_2$ satisfying $|S_1| + |S_2| = |S|$. Now repeat.


Algorithm: given very large file of strings, find lines containing substring

You can construct a suffix tree for that very large file and once generated the same can be used for querying.
For Suffix tree generation use Suffix Array approach, there are many algorithm to generate suffix array.
This is a taxonomy of many suffix array algorithm available today
http://www.cas.mcmaster.ca/~bill/best/algorithms/07Taxonomy.pdf

To starts with I would recommend prefix-doubling which required O(n log(n)) time.
You can then look at DC3 which does the job in O(n) time.


How does a hard drive knows what bit is the beginning of of a byte/word?

Simplified, the operating system sees disk storage as a randomly accessible set of sectors, each sector containing some fixed number of bytes.  The OS asks the disk controller for a sector using some standard protocol and it is the responsibility of the disk controller to retrieve the sector with the bits and bytes in the same order in which they were written.  The communication protocol (e.g. SCSI) specifies both bit and byte order for reads and writes so there is no space for confusion about where the data starts and stops.

Operating systems can and do take into account the characteristics of storage media for the sake of efficiency, such as existence of onboard cache, rotational delays, and head movement, but those things have no bearing on where bytes and sectors start.


Definition of Closed Under Left Polynomial Composition

The correct interpretation is as follows. A class $\mathcal{C}$ is closed under left polynomial composition if the following holds:

For any $f(n) \in \mathcal{C}$ and any polynomial $p(n)$ there exists $g(n) \in \mathcal{C}$ such that $p(f(n)) = O(g(n))$.

In particular, the class $O(n)$ isn't closed under left polynomial composition.
Why are we interested in this definition? Here is an example. We can convert a $k$-tape Turing machine running in time $T(n)$ into a single-tape Turing machine running in time $5kT(n)$, see this question. If we start with a multi-tape Turing machine running in linear time, we don't necessarily end up with a single-tape Turing machine running in linear time. But if we start with a multi-tape Turing machine running in polynomial time, then we do end up with a single-tape Turing machine running in linear time. It thus makes sense that $O(n)$ isn't closed under left polynomial composition, but $n^{O(1)}$ is.


Why substituting the search part in INSERTION SORT doesnt yield a running time of $\Theta(nlgn)$

You still need to shift $O(n)$ elements to make room for the newly inserted element even if you find the correct position in $O(\log n)$.


Do not even mention big-O here because that is for asymptotic behaviour and f(1000) doesn’t give you the slightest clue what f(2000000) would be.

You are given that the runtime is f(n) = c x g(n) for three different functions c. Given the value of c x g(1000) for the first function g, you calculate c. Then you substitute c and n for all the cases.


Complexity of checking whether linear equations have a positive solution

First, this can be solved by linear programming. Let $x_1$, $x_2$, $\ldots$, $x_n$ be your variables. The linear program that solves your question is then

$\max t$
subject to
$t \leq x_i$, for $i=1 ... n$,
$Ax = 0$.

If the maximum is 0, then there is no positive solution. If the maximum is $\infty$ (i.e., the linear program is unbounded) then there is a positive solution.

Second, using standard transformations on linear programs, the feasibility problem for an arbitrary linear program with strict inequalities can be reduced to your problem. We start with the feasibility problem

Does there exist $x$ such that
$A x < b$ ?

We can now add a new variable $x_{n+1}$ to the right-hand-side of all these equations and an inequality $x_{n+1} > 0$ to make everything homogeneous. So for the $k$th equation, we now have

$a_{k,1} x_1 + \ldots + a_{k,n} x_n - b_k x_{n+1} < 0$.

This gives an equivalent problem on a new matrix $A'$:

Does there exist $x$ such that
$A'x < 0$ ?

Next, we can turn the inequalities into equations by adding some variables $y_i$ and requiring that $y_i > 0$. The $k$th equation on the new problem turns into

$a'_{k,1} x_1 + \ldots + a'_{k,n} x_n + a'_{k,n+1} x_{n+1} +y_k = 0$.

Finally, we want to allow all the variables to be positive. How we do this? For every variable $x_i$ with an arbitrary sign, we replace $x_i$ by $z_i - w_i$, and require $z_i>0$, $w_i > 0$.

The feasibility problem is essentially as hard as an arbitrary linear programming problem, so in general there won't be any easier way to solve your problem than using linear programming.


How to detect infinite loop exist in linear bounded automata (LBA)?

The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ causes it to be assume configurations $c_1, \dots, c_n$ and $c_n = c_1$, then $M$ will repeat the loop $c_1, \ldots, c_n$ indefinitely.


Hadamard transformation and measurement of one qubit

I'm not the best person to answer your question but I'll give it a try.

1st Question:

You do not yet make a measurement after applying the Hadamard Operator on your first qubit. Afterwards say you make a measurement on your 1st qubit, the state you'll end up with is:

$|\psi>_{post-measurement}$ = $1/\sqrt{p_1(m)}$ $\sum_{j} c_{mj} |m>_1 |j>_2$

whereby $m$ is the measurement result of your 1st qubit (either 0 or 1) , $p_1(m)$ is the probability of getting that result on your 1st qubit, $c_{mj}$ the usual coefficient infront of your ket.

2nd Question:

This will answer how to get ${p_1(m)}$.
Write out the density matrix of $|\psi>_{pre-measurement}$, then trace out the 2nd qubit. Then apply bra-ket to your reduced density matrix:

${p_1(m)}$ = $<m|_{1}$ $\rho_{1} |m>_{1}$

Or equivalently:

${p_1(m)}$ = $\sum_{n}|<m|_1<n|_2 \sum_{ij} c_{ij} |i>_1|j>_2|^2$


Let $F_n$ be a random involution induced by a random perfect matching on $\{0,1\}^n$. For any input $x$, the distributions of $F_n(x)$ and $R_n(x)$ are almost identical (in fact, $F_n(x)$ has the same distribution as $R_n(x)$ conditioned on the event $R_n(x) \neq x$, which occurs with probability $1-2^{-n}$), so they are statistically indistinguishable. However, $H_n$ is the identity function, so it is easy to distinguish from a random function.

With some more work, it might be possible to extend this from one query to any fixed polynomial number of queries.


How to find the closest N to the power of X to the given number?

Here is a general solution for the following problem:

  Given a positive integer $m$, find positive integers $a,b \geq 2$ such that $a^b$ is as close as possible to $m$.

Let $n$ be the length of $m$ in bits (so $n = \Theta(\log m)$). If $2^b > m$ then there is no point to check any $b_0 > b$, hence we only need to check $O(\log m) = O(n)$ many different values of $b$ (we can find the maximal $b$ by comparing $2^b$ to $m$). For each value of $b$, we can find the best value of $a$ using binary search; this takes polynomial time for each $b$, and so polynomial time overall. Finally, we choose the optimal solution among the $O(\log m)$ possibilities.


Do I require loading in this example of load store architecture?

You need to load x into R before you store R into b

wikipedia says:

In computer engineering a load/store architecture only allows memory to be accessed by load and store operations, and all values for an operation need to be loaded from memory and be present in registers. Following the operation, the result needs to be stored back to memory.

In your case, x is still in memory and has to be loaded into a register.


Regular language? Union of the dictionary and an non-regular language

The best way to see that $L_1 \cup L_2$ is not regular is through closure properties of the regular languages.

Theorem. If $L_1$ is finite and $L_2$ is not regular, then $L_1 \cup L_2$ is not regular.

Proof. Since $L_1 \setminus L_2$ is finite, it is regular.
Suppose $L = L_1 \cup L_2$ were regular. Then $L \setminus (L_1 \setminus L_2) = L_2$ would also be regular, contrary to assumption. $\qquad\square$


Proving a language is not a regular language but a context free language

While it is possible to show that $L_2$ is not regular using the pumping lemma, it is easier to do so by making use of the fact that the regular languages are close under complement, i.e. a language is regular if and only if its complement is regular.

In order to show that $L_2$ is context-free, you can give either an automaton or a context-free grammar for the language. The automaton is presumably the easier way in this case. Hint: $L_2$ is a deterministic context-free language, so there is a deterministic PDA for $L_2$ that can be derived in a straightforward way from the deterministic PDA of $L_2$'s complement.


Possible solutions how to find all points (given by lat, long) that are within a radius from main point

You can speed up your search by using a datastructure like a kd-tree or an r-tree. The basic idea is to divide your space into boxes and store the mapping from points to boxes (and back) in a way that allows for quick lookup times. Then you don't have to calculate the distances to all points to see which are too far away, you can restrict your search to points in the same (or adjacent) boxes.

But note that the naive approach is actually pretty good in this case, even if it's asymptotically not optimal. CPUs are really good at summing squares and it's trivial to throw more cores at the problem if you need more speed. So unless you're dealing with many points, it will be hard to beat.


Find out the largest LCM of the partitions of n

It seems that this a competition problem. Your best bet is to pre-calculate maximum values for all numbers(250 isn't very big) and store it into an array. That would be the best bet as this can give you timing near to zero.


NFA that accepts all numbers not divisible by 105

Here is a hint.

$L$ is the union of the following three languages.

$L_3=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 3}\}$,
$L_5=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 5}\}$,
$L_7=\{{a^n \mid n\ge1\text{ and }n \not=0 \mod 7}\}$.

Construct the DFA for the above three languages. Then combine them together.

Exercise. (It may take some time to do this exercise.) Show that no NFA with less than 15 states accepts $L$ exactly.


Your interpretation of the $G$ modality is incorrect; it does not inherently talk about all paths. In particular, the example you give specifies that there is a path such that from some point on, all states on that path satisfy $p$.

As you suspect, for CTL* it is in general not possible to use a simple bottom-up evaluation, as you would for CTL, the reason being the LTL-like nested temporal operators.


The proof that $\mathsf{NL} \subseteq \mathsf{AC}^1$ is constructive, giving an $\mathsf{AC}^1$ circuit for directed reachability. Since directed reachability is $\mathsf{NL}$-complete and 2SAT is in $\mathsf{NL}$, there is an $\mathsf{AC}^0$ reduction from 2SAT to directed reachability. Combining the $\mathsf{AC}^1$ circuit for directed reachability with the $\mathsf{AC}^0$ reduction from 2SAT to directed reachability, we obtain an $\mathsf{AC}^1$ circuit for 2SAT.

It might be better, however, to construct such a circuit directly using ideas from the proof of $\mathsf{NL} \subseteq \mathsf{AC}^1$. This could result is a smaller and simpler circuit.

The OP also asks whether HornSAT has $\mathsf{AC}^1$ circuits. Since HornSAT is $\mathsf{P}$-complete and we believe that $\mathsf{AC}^1 \neq \mathsf{P}$, the answer is probably no. The OP suggests using the switching lemma to prove this. However, the switching lemma only works for circuits of depth $O(\log n/\log\log n)$.


Are all foldable data structures also recursive?

No, not all foldable data structures are recursive, although the in the non-recursive case what we have is really a degenerate version of a fold.

For example, we can view the function if : Bool -> a -> a -> a as a fold over the type Bool.

In general, when dealing with recursive or non-recursive types, the fold are called eliminators, since they are how we consume values of a given datatype. Eliminators are particularly interesting for dependent types and indexed type families, where the eliminator corresponds to an induction principle for that data type. See this paper for more info on this.

Eliminators always terminate, which means that if you have only eliminators (in place of general recursion) you will not be Turing Complete. You can even encode a data structure as its eliminator, using something called Church Encodings. Using this, you can write lists and other data types in a language that only has functions, like System F.


Number of 1 child nodes in a binary tree

Try to construct a tree with a lot of 1-child nodes. Start with the root. Let's say the root has exactly one child. Let's say that that child itself has exactly one child, etc.

   So in a tree with $n$ nodes, you can arrange for all but one to have a single child. This means the maximum is at least $n-1$, and of course it's at most $n$. Finally, prove that the maximum isn't $n$: there has to be at least one leaf (0-child node).

I think the maximum over trees of a given depth is a little more interesting. What's the maximum number of 1-child nodes you can cram in a binary tree of depth $n$?

For depth $0$, there's a single leaf, so the maximum is $0$. For depth $1$, enumeration shows that the maximum is $1$. More generally, what tree shape maximizes the number of one-child nodes?


How do you detect if an algorithm is running at O(nlogn)?

I would like to apologize for sloppy notation in advance.

Recall that $\log_2 10^{10} < 34$, so that for any practical purposes, $O(n \log n)$ will be bounded by $34 \cdot O(n)$, which of course is $O(n)$ (again for all practical purposes).

That means that if language A is 34 times faster than language B, then an $O(n)$ algorithm in B is indistinguishable from an $O(n \log n)$ algorithm in language A.

In practice, it's not possible without a theoretical analysis of the algorithm.

However, it's often simpler to distinguish an $O(n \log n)$ algorithm from an $O(n^2)$ algorithm (in the same language, at least), although we do have problems distinguishing an $O(n \log n)$ algorithm in Python from an efficient $O(n^2)$ in C/C++ in programming contests.


Converting a algorithm to a runtime function

The recursion for $g$'s running time is $$T(n)=n(T(n-1)+1)$$ where $1$ is the (constant) work done from the print statement and incrementing $k$. $g(n-1,k)$ and the constant work are called $n$ times from the for loop.
The recursion stops at $g(0,k)$ which has running time $T(0)=1$.

Solving this recursion on Mathematica (I suspect doing it by hand would involve induction or inspection) gave the result:
$$T(n)=\Gamma(n+1)+en\Gamma(n,1)$$
The complexity of this is
$$T(n)=O(\Gamma(n+1)+en\Gamma(n,1))$$
$$T(n)=O(n\Gamma(n,1))$$
Since $n$ is an integer, then we can reduce this to
$$T(n)=O(n!)$$


Calculating miss rates of word-addressable and direct-mapped cache

It seems you don't understand how cache lines work. A cache line is a contiguous chunk of memory. In this example, the cache line size is 32 bytes. This means that 32 contiguous bytes are always loaded into the cache at a time, namely whenever a miss occurs.

So if we initially assume the cache is empty (or "cold"), then the first access will be a miss. However, the first 28 bytes will be loaded in. This means that in addition to loading word 0 into the cache, the words at addresses 4, 8, 12, 16, 20, 24, and 28 will also get loaded into the cache. Conveniently, this is how your example program accesses data (linearly), so we will get a cache hit for all of those words. When we hit the word at address 32 we will again get a miss and the process repeats. Thus, our miss rate is 1/8, once for every 32 byte block.

Since we are never accessing the same data more than once, the size of the cache itself is irrelevant, i.e. all we need is for the cache to be able to hold a single line. Thus, we can not reduce our miss rate with a larger cache.

And finally, as shown from the analysis, the size of the data set is irrelevant. It doesn't matter if we're reading in 1 Kilobyte or 1 Gigabyte, the miss rate is the same.


Finding minimum/maximum value in a Binary Indexed Tree

You cannot do better than $O(n)$.

Consider a set, where all values are $k$, except $2i$ and $2i-1$, which are $k-l$ and $k+l$ respectively. Any entry in the tree that contains a sum of $m$ values will be $mk$, with the single exception of the entry $2i-1$.

Thus, even if we knew we had a set of the form described, we had to look at $\frac n2$ entries in the worst case, in order to determine the minimum and maximum value.


The difference he is making is between long-term and short-term goals. Both need to be definable, and there is obviously a mutual dependency between these two sets of goals, so you can think of pressing the red button as something that will also have to be treated within this framework. You can then imagine that if pressing the button has the same utility of your present long-term goal, that would cause the button to be pressed imediately, whereas if it had the same utility of any of your immediate and cheaper short-term goals (because it would be normalized that way), it could ideally go unnoticed, meaning that it would be made uninteresting as an action, but not as a result. He then immediately addresses the need to consider the existence of the button in long-term goal scenarios, so there's no free lunch here.

This is evidently an oversimplification made for didactic purposes. The idea is not to show exactly how difficult is the problem, but that it is more complicated than common sense would conceive.


ID3 is a heuristic. It is not guaranteed to generate an optimal decision tree.
Here is an algorithm for Exercise 1:

If $X_3 = 1$, then answer $2X_1-1$.
If $X_3 = 0$, then answer $2X_4-1$.

For Exercise 2, suppose $f_k = X_1 \lor \cdots \lor X_k$. An optimal decision tree simulates the following algorithm:

If $X_1 = 1$, output 1, else continue.
If $X_2 = 1$, output 1, else continue.
...
If $X_k = 1$, output 1, else output 0.

Indeed, every decision tree for $f_k$ must query all of $X_1,\ldots,X_k$ in the worst case.


Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Nope. In order to find the distance from $s$ to $t$ it is necessary to determine the length of all paths that are at least at the same distance as $t$ is. If $t$ has a "median" distance half of the distances will be known that way.

In certain application areas (with an exponentially sized "implicit" state space) it can still be worthwhile to start searching from both sides and look for nodes that are found in the middle.


Adding two numbers in base 2(floating point) vs Multiplying two numbers in base 2(floating point)

Floating point numbers are stored as $x \cdot 2^e$, where typically $1 \leq x < 2$ (unless your number is denormalized). When multiplying $x \cdot 2^e$ and $y \cdot 2^f$, we simply compute $xy \cdot 2^{e+f}$ (we have to truncate $xy$). When adding $x \cdot 2^e$ and $y \cdot 2^f$, we first have to shift one of the numbers (the one with smaller exponent) so that we have a "common denominator". For example, to add $1 \cdot 2^0$ and $1 \cdot 2^{-3}$, you have to rewrite the latter as $0.125 \cdot 2^0$.
Whether this makes addition more complex than multiplication is a matter of opinion. Multiplying $x$ and $y$ is still harder than addition.


Hardness amplification of PRFs by increasing key length

It's important to be clear about what is the purpose of the GGM construction.  The GGM construction is designed to build a PRG out of a PRF: i.e., to construct one primitive, given an instance of a different primitive.  It's not designed to increase the security of the underlying primitive.

This is a general theme in a lot of provable cryptography: you have to start with a primitive that is secure; then you can build other things out of it, but the primitive you start with has to be secure, or else you can't do anything.  The standard constructions don't increase the security of the basic primitive; instead, that's the job of the person who designed the basic primitive.

Hardness amplification is a different task.  Hardness amplification means: given a primitive of type T, build another primitive type T that is more secure (in some sense).  In general, provably-secure hardness amplification is very difficult to achieve.  Why?  Well, we don't know how to build any crypto algorithm that is provably secure; all we know is conditional results (if you give me a secure one-way function, then I can build other things that are secure).

There are some examples of techniques that given a $(t,\epsilon)$-scheme construct a new scheme that is something like $(t,\epsilon^2)$-secure, but that's different.  (If you're interested in that, spend some quality time with Google and Google Scholar looking at results on "hardness amplification"; see, e.g., Yao's XOR lemma.)  I don't know of any techniques that given a $(t,\epsilon)$-scheme construct a $(t^2,\epsilon)$-scheme.


Of course your approach will work but the answer to your question: "Does this solution make sense?" is entirely dependent on the situation.

Priority Queues are used (e.g.) when you want to serve the passenger whoever's destination floor is closest to the current one. Said passenger will have very high priority. This has a disadvantage that when a passenger wants to go to a floor that is far away from the current one,  he will be assigned a very low priority and will be served never/late. This can be solved by increasing the priority for a passenger over time.

Your approach has the advantage that there's a maximum waiting time known for all passengers. That is, the time it takes for a person to go to floor 1 when he gets in at floor 2 while the elevator is going up all the way to the penthouse and it stops at all floors along the way. The advantage of knowing this isn't present in the case (or it is at least not easy)  in the priority queue approach. But you can imagine that the situation described can be very annoying for the involved passenger since he will have to travel along the full building almost twice to lower just one floor.

Another approach I'm thinking of while writing this makes use of priority queues where the priority of going to a floor is the number of people that needs to get in/off at that floor.

In conclusion,  I think the advantage of your approach isn't very useful and it has a big disadvantage as well. I would look into priority queues and then define for yourself what priority means. Maybe your priority is to deliver groups of people to floors at once (last approach) or maybe it's to deliver the passenger whoever's floor is closest, (first approach). As said before,  deciding if an approach is good depends entirely on the situation.


The first solution coming to mind is an extension of Brzozowski's derivatives as context-free grammars are closed under derivative operation with respect to a letter.

Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to


Finding independent set of size n in an undirected graph

(Note: for the sake of standardization, I'm using $n$ for the number of vertices in the graph, and $k$ for the number you want in your independent set.)

The problem of whether such a set even exists is actually NP-complete, by reduction from the clique problem (since an independent set is a clique in the complement of the graph). So unless P=NP, you're not going to get any better than exponential time. This limits you to rather small graphs in practice.

The easiest algorithm for this is simple brute force: run through all sets of $k$ distinct vertices, and check whether each one is independent. If it is, return it. As expected for brute force, this runs in $O(n^2 2^n)$. An improvement was found by Xiao and Nagamochi in 2017, which brings this down to about $O(1.2^n)$. (Unfortunately, I don't have access to their paper, so I can't summarize their algorithm here.)


Could anyone prove why O(n^(log n)) < O((log n)^n)?

Using $ < $ with the big-oh notation is a bit of abuse of notation.
Formally, I take your statement to mean $\forall f(n) \in O(n^{\log n}), \; f(n) \in O((\log n)^n)$.

Let $f(n) \in O(n^{\log n})$, by definition of big-oh we know that the function is eventually bounded from above by $c n^{\log n}$ for some constant $c > 0$.
Then, for sufficiently large $n$,
$$
f(n) \le c n^{\log n} = c 2^{\log(n^{\log n})} = c2^{\log^2 n} < c2^n < c (\log n)^n,
$$
showing that $f(n) \in O((\log n)^n)$.

In particular the constant c in the last term can be made arbitrarily small. Indeed $n^{\log n} \in o((\log n)^n)$. A simple way to see this is by taking the limit of the ratio of the two functions:

$$
\lim_{n \to \infty} \frac{n^{\log n}}{(\log n)^n} =
\lim_{n \to \infty} \frac{2^{\log^2 n}}{2^{n \log n}} =
2^{\lim_{n \to \infty} \log^2 n - n \log n} = 0
$$


Do we need to check for mantissa overflow in floating point multiplication?

When we multiply, the answer is stored in 2 registers. When we multiply 2 numbers the results length does not exceed  ($n_1+n_2$) where $n_1$ is length of 1st number and $n_2$ is length of second number. So there is no chance of overflow here as the length of 2 registers is greater than or equal to $n_1+n_2$.


What is oblivious RAM and how does it work?

Oblivious RAM is an interface between a program and the physical RAM that when you perform a read or write, does both at the same time on the physical RAM to hide if you are reading or writing. Plus, it shuffles the memory from time to time so that an adversary seeing only accesses to the physical RAM cannot know whetever you accessed the same data twice or accessed two different data. Thus hiding the access patterns to the physical RAM.

Instantiations I know of rely on oblivious sort, which is a way of sorting elements in a list by comparing and eventually swapping elements in an order predefined, that does not depend on the comparison results.


Your problem is hard, but not too hard.

Start with a subproblem: For one material, you have various package sizes with different cost. You also require a certain amount of material. Find the cheapest way to buy your material.

To do that, use dynamic programming: Let's say you need 5000 units. Find in turn the cheapest way to buy at least 1, 2, 3, ..., 5000 units. The cheapest way for 0 units is buying nothing. To buy at least K units, you either buy one package with size >= K, or you buy one package with size k < K, then buy packages with total size at least K - k at the lowest possible price. Of the choices you have, you use the cheapest one.

Second subproblem: Find all sets of possible suppliers. Just try all possible subsets - for n suppliers there are $2^n$ possible subsets of suppliers, and reject all subsets that don't contain any supplier for a material that is required.

Then for each possibe subset of suppliers, find the cheapest way to buy each material. Add up the cost for the materials, plus the delivery cost. And then take the subset of suppliers that was cheapest.

For small problem sizes, this shouldn't take too long. Of course the problem looks NP-complete if you turn it into a decision problem, so your execution time will grow exponentially with the problem size.

Finding the cheapest way to buy each material seems to be the most time critical. Think how you can optimise it by finding packages you should never buy (if you have a pack of 25 costing 12, and a pack of 24 costing 13, you would never buy the 24), and amounts you don't care about (in your example with pack sizes 100, 200 and 500, your total is always a multiple of 100).


What is the optimal way to perform GCD chain operation?

You are saying that you will perform n-1 gcd operations, unless you find k numbers with a gcd of 1 by performing k-1 gcd operations.

Since you don't know which set of numbers has a gcd of 1, you can't pick a set with gcd 1. Your total time depends on the data you have.

You can try to process small numbers first, because the gcd of small numbers tends to be calculated quicker than the gcd of large numbers.

The optimal strategy will not always lead to the best outcome. I put a deck of cards on the table, face down, and ask you to pick the ace of hearts. Do you think "pick the ace of hearts" is the optimal strategy? No, it isn't a strategy that you can enforce since you don't know which one is the ace of hearts.


Notice that a data structure stores more than just it's accessible elements. This is probably what mean by additional feature, but I would consider it the essential feature. Take for example a binary search tree. This tree stores information on the order of its elements. In particular, by a traversal you can output the sorted sequence of elements stored in the tree in linear time. There are roughly $\Theta(4^n)$ different full binary trees with $n$ leaves. Thus the  data structure stores roughly $2n$ additional bits in this case.

Maybe this view helps. Some algorithmic problems are one-shot problems. So you take the input, process it, and then (hopefully) output the solution. Other problems, however, are trying to solve several problems for which part of the input is mostly the same. Here it might pay off to preprocess the static input (the data), such that further requests are easier to answer. The result of the preprocessing is stored (often in form of a labeled graph). This is what you do, when you store data in a data structure.

The above paragraph explained how static data structure behave. Usually data structures are dynamic, allowing you to alter the represented data and its associated information.


Constructively deciding whether a decidable predicate holds universally

You are asking for a constructive proof of the Lesser limited principle of omniscience (LLPO), which states (in one of its forms) that for a decidable proposition $P$ on natural numbers
$$(\forall n \in \mathbb{N} \,.\, P(n)) \lor \lnot \forall n \in \mathbb{N} \,.\, P(n).$$
That's exactly your problem. It is well known that LLPO is not provable constructively.

Unless you have some further conditions on $P$ which you did not tell us about, you're stuck.


Shortest path where weights are computationally expensive to calculate

The problem you are concerned with has been examined also in the literature. See the paper Szepesvári, C. 2004. Shorteset path discovery problems: A framework, algorithms and experimental results. Association for the Advancement of Artificial Intelligence 2004, pp. 550--555.. In this paper, the following is said at the very beginning:

  In this paper we introduce and study Shortest Path Discovery
  (SPD) problems, a generalization of shortest
  path problems: In SPD one is given a directed edge-weighted
  graph and the task is to find the shortest
  path for fixed source and target nodes such that initially
  the edge-weights are unknown, but they can be queried.
  Querying the cost of an edge is expensive and hence the
  goal is to minimize the total number of edge cost queries
  executed.

Note that this work assumes edge costs to be unknown. A practical application of this theoretical assumption arise (as mentioned above) in those cases where querying the cost of an edge is very expensive ---as in your case. The algorithms considered in this paper are sound and they attempt at reducing the number of queries.

It seems, however, that your question also refers to the applicability of typical search algorithms such as A$^*$. Recall that A$^*$ expands all nodes $n$ such that $f(n)<f^*(s)$ where $f(n)=g(n)+h(n)$. In other words, it has to expand necessarily all nodes with an $f$-value which is lower than the cost of the optimal solution. The answer provided by Tom van der Zanden goes in this direction indeed. However, truth is that A$^*$ also generates (thus, it evaluates and stores in OPEN) a number of nodes with $f(n)\geq f^*(s)$ which are absolutely unnecessary.

This problem is of importance since the number of nodes generated grows exponentially with the depth of the search traversed. In your case it is twice importance because that extra amount of nodes have to be evaluated (and this requires querying a function its edge cost). A number of strategies have been proposed to save those extra generations in the context of A$^*$. For a good introduction and a plausible solution to this problem see: Meir Goldenberg, Ariel Felner, Nathan Sturtevant, Robert Holte, Jonathan Schaeffer. Optimal-Generation Variants of EPEA$^*$, Proceedings of the Fifth International Symposium on Combinatorial Search, (SoCS-2013), July 2013 In case this paper fits your needs check the publications page by Ariel Felner because he also contributed with an additional paper.

Hope this helps,


Word tiling, where you must use each tile exactly once

I can't speak to whether it's a known problem, but it is NP-complete.

It's clearly in NP, so we just have to show NP-hardness. The following reduction is from the strongly NP-hard 3-partition problem, which asks, given a multiset of positive integers $[x_1,\ldots,x_{3m}]$, whether there exists a partition into $m$ submultisets such that the sum of each submultiset is equal to the integer $s=\frac{1}{m}\sum_{i=1}^{3m}x_i$. For each $i\in\{1,\ldots,3m\}$, make a string $a^{x_i}$. Make $m-1$ strings $b$. The target word $w$ is

$$a^sba^sb\cdots ba^s.$$


Regular language as finite union of periodic sets

The answer by @YuvalFilmus is perfectly fine, and points you to the import notion of star height. But let me add a little bit more. We will show that languages of your form give a proper subset of the languages of star height one. But first, some musings what might come close to your form.
General Regular Languages
First, probably the closest form to yours for regular $L \subseteq \Sigma^*$, accepted by a complete deterministic automaton $A = (\Sigma, Q, \delta, q_0, F)$.
For $q \in Q$ and $E \subseteq Q$, write $L_{q, E}(A)$ for the language
accepted by $(\Sigma, Q, \delta, q, E)$, i.e., changing the start state to $q$
and the set of final states to $E$.
Then, we can write
$$
 L = \bigcup_{ q \in F } L_{q_0, q}(A) L_{q, \{q\}}(A)^*
$$
This result seems to be folklore and follows easily. A more refined variant of this decomposition appears in the book Automata, Languages and Machines, Volume A by S. Eilenberg, under the name iterated up-decomposition.
Commutative and Bounded Regular Languages
Others forms, more close to yours, and being proper generalizations of the unary language case you mentioned, could be given for the bounded and commutative regular languages. A language is commutative, if it is closed under permutation of letters. For example, $\{ab,ba\}$ is commutative, whereas $\{ab\}$ is not. A language $L \subseteq \Sigma^*$ is bounded, if $L \subseteq w_1^* \cdots w_n^*$
for words $w_i \in \Sigma^*$. In what follows, let us denote by $\diamond$ the shuffle of two languages, and, for $L \subseteq \Sigma^*$, by $L^{\diamond,*} = \bigcup_{n \ge 0} \underbrace{L \diamond \ldots \diamond L}_{\mbox{$n$ times}}$ the iterated shuffle. Also, by $\operatorname{perm} : 2^{\Sigma^*} \to 2^{\Sigma*}$ denote the permutational closure, or commutative closure, i.e. adding all words that are permutations.
For example, $\operatorname{perm}(\{ab\}) = \{ab,ba\}$.
Note that $L \subseteq w^*$ is regular iff  $L = w^n(w^p)^*$ for some $n, p \ge 0$. This is implied by noting that $\{ n : w^n \in L \}$ is ultimately periodic (it could be viewed as a regular unary language).
By a result of Ginsburg/Spanier we have

A language $L \subseteq w_1^* \cdots w_r^*$ is regular iff it is a finite union of languages of the form $L_1 \cdots L_r$, where each $L_i \subseteq w_i^*$ is regular.

Also, if $\Sigma = \{a_1, \ldots, a_k\}$ and $L \subseteq \Sigma^*$ is commutative and regular, it is possible to show that
$$
 L = \bigcup_{i=1}^n \operatorname{perm}(u_i) \diamond \operatorname{perm}(N_i)^{\diamond,*}
$$
for finite sets $N_i \subseteq a_1^* \cup \ldots \cup a_k^*$ with $|N_i \cap a_j^*| \le 1$.
Also, as stated here and here, a regular language $L$ over $\Sigma = \{a_1, \ldots, a_k\}$ is commutative iff
$$
 L = \bigcup_{i=1}^n U_{i,1} \diamond \ldots \diamond U_{i,k}
$$
for unary regular languages $U_{i,j} \subseteq a_j^*$
with $i \in \{1,\ldots, n\}$ and $j \in \{1,\ldots,k\}$.
All these results are closely related. Note that for unary languages, they all reduce to the form you have stated.
A Necessary Condition for Languages of your Form
The condition I will state involves topology and infinite words. It yields, for example, that $b^*a$ and $(b^*a)^*$ could not be written in your form. The latter has star height two, note that star height could be characterized by cycle rank, see Eggan's Theorem.
However, I do want to give a self-contained, and different, argument here, not based on star height. Let $\Sigma^{\omega}$ be the set of infinite words over $\Sigma$. Define an operator $W : 2^{\Sigma^*} \to 2^{\Sigma^{\omega}}$ by, for $L \subseteq \Sigma^*$,
$$
 W(L) = \{ \xi \in \Sigma^{\omega} \mid \mbox{ $\xi$ has infinitely many prefixes in $L$ } \}.
$$
Then
\begin{align*}
 W(b^*a) & = \emptyset \\
 W((b^*a)^*) & = \{ \xi \in \Sigma^{\omega} \mid \mbox{$\xi$ has infinitely many $a$'s. } \}.
\end{align*}
Observe that
$$
 W(U \cup V) = W(U) \cup V(V),
$$
as, if $\xi \in W(U\cup V)$, then, by the pigenhole principle, at least one of $U$ or $V$, or both, must contain infinitely many prefixes of $\xi$. Also, in your form we could assume all the sets $A_i$ are singletons, as concatenation distributes over union.
Let us inspect languages of the form $L = u(u_1 + \ldots + u_n)^*$, which are the parts of your form.
Set $\Gamma = \{ b_1, \ldots, b_n \}$, an auxiliary alphabet, and consider the homomorphism $h : \Gamma \to \Sigma^*$ given by $h(b_i) = u_i$, i.e., substituting each letter by the corresponding word. This homomorphism could also be applied to infinite words in $\Gamma^{\omega}$. We have
$$
 W(u(u_1 + \ldots + u_n)^*) = \{ uh(\xi) \mid \xi \in \Gamma^{\omega} \}.
$$
In particular, if all the set $B_i$ are singletons, $W(L)$ is finite, and $W(L) \ne \emptyset$ for every infinite language of your form.
By the last observation, $b^*a$ could not be written in your form. So, this is a very simple example, even of star height one.
But let us show that $L = (b^*a)^*$ could also not be written that way. Assume it could be, then the set of infinite words, which all have an infinite number of $a$'s in it, could be written in terms of a homomorphism
$h : \Gamma^* \to \Sigma^*$ as outlined above, i.e.,
$$
 \{ \xi \in \Sigma^{\omega} \mid \mbox{$\xi$ has infinitely many $a$'s. } \} = u h(\Gamma^{\omega})
$$
for some $u \in \Sigma^*$.
Let $m = \{ |h(x)| : x \in \Gamma \} + |u|$.
Then $ub^maaaaa\cdots$ is in this language,
and this implies $h(x) \in b^+$ for some $x \in \Gamma$.
But then $ubbbbbbb\cdots \in uh(\Gamma^{\omega})$, which is a contradiction, as it only contains a finite number of $a$'s. Hence, $(b^*a)^*$ could not be written that way. $\square$


Shortest path in graph by flipping binary colored nodes to one color

This problem is $NP$-complete, there is a quite simple reduction from Hamiltonian Path. Therefore, there's (likely) no way to solve this problem efficiently in general, so the solution method will need to be tailored to the inputs you are interested in solving (brute force for small instances, heuristic methods for large instances, specialized methods for instances with special structure,...).


Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of its variants for instance. It's common for the soundness of a type system to boil down to proving that all programs normalize in it. Strong normalization is a very desirable property in general in programming languages research.

I haven't seen a lot of success in catching infinite loops in practice however "Ensuring Termination in ESFP" by Telford and Turner shows a more robust termination checker that was able to prove that Euclid's algorithm always terminated and handles partial cases. Euclid's algorithm is a famously tricky example of a primitive recursive function that isn't straightforwardly provable to be primitive recursive. It fails checkers that simply look for a decreasing parameter (or some simple pattern of decreasing parameters like Foetus termination checker). To implement this using primitive recursive combinators you have to encode a proof of termination for the algorithm as a parameter in the function essentially.

I can't think of any results for procedural languages off the top of my head and most results in functional languages use some kind of restriction that makes the obviously terminate rather than trying to perform some kind of complex analysis to ensure that more natural programs terminate.


Is there a name for a compiler that runs once at runtime right before a program is executed?

Nope, it's not a JIT, it is just an ordinary compiler.  There's no special name needed -- it's a compiler.
In this context "run time" means when the program being compiled is in the middle of executing.


Can a graph have multiple identical elements?

Graphs don't have values.  Graphs don't hold numbers.  You don't insert a value into a graph.  Graphs have vertices and edges.

You can augment a graph to associate each vertex (node) with a number, if you wish.  If you do that, it's up to you to define whether or not you allow two different vertices to have the same number or not.  There is no universal answer.


Which flow algorithm on a graph is used when the capacity is a rational number?

Since all steps of the algorithm merely involve addition, you can compute the least common multiple $m$ of the denominators of all weights involved, and creating $G'$ from $G$ by multiplying all weights by $m$.

Then all weights are integers and you can run Ford-Fulkerson. You can divide the results from it by $m$ again to get back your rationals.


So here is the main idea behind this fact. Let us denote by $C$ all possible configuration of the $l(n)$-space bounded TM. Notice that $|C|\le 2^{c\cdot l(n)}$, where $c$ is a constant depending on $M$.

We assume that the input tape is a two-way tape. Let $w$ be a word of size $n$, such that for all smaller words $u$ we have $l(w)>l(u)$. When the head moves from position $i$ to position $i+1$ on the input tape, or vice versa, we record the current configuration of the computation in the crossing sequence $C_i$. Assume we have $i\neq j$ with $C_i=C_j$. Then we define as $w'$ the word obtained from $w$ by deleting everything between the characters number $i$ and $j$. We observe that $w'$ is a shorter word which uses the same amount of space. Contradiction, there is no such $w$.

If $l(n)\in o(\log\log n)$ then you have $o(\log n)$ configurations and $o(n)$ crossing sequences. Hence two crossing sequences are the same.

Notice that if your input tape is 1-way, then even with $o(\log n)$ space you are doomed.


If problem is coNL-complete, is it NL-complete

If the language $A$ is $NL$-complete then

$A \in NL$
Each problem in $NL$ is logspace reducible to $A$

Since $coNL = NL$ each problem in $coNL$ is logspace reducible to $A$ as well. Thus $A$ is $coNL$-complete.


What additional expressivity does polyvariance give in pushdown CFA?

After playing with an implementation (found here), I believe I've figured it out.

Although 0PDCFA technically entirely eliminates return-flow merging, this isn't a very strong result in the absence of any polyvariance: if the same function is called in two different contexts, the analysis must end up merging flows within the body of the function, since multiple values are bound to the same variable and the variable's abstract address is identified with its name. 1PDCFA provides a different set of addresses to each syntactically distinct call of each function (I might be either under- or over-selling here), eliminating much of the merging.


Algorithm for using power series to numerically solve a partial differential equation given a boundary condition?

Instead of building a polynomial and trying to deduce the equation on the coefficients, you can just derive it directly from a general term coefficient

>>> i, j, x1, x2 = symbols('i j x1 x2')
>>> a = IndexedBase('a')
>>> u = Function('u')
>>> pde = u(x1, x2).diff(x1, 2) - u(x1, x2).diff(x2, 2)
>>> term = a[i, j]*x1**i*x2**j
>>> pdeterm = powsimp(pde.replace(u, Lambda((x1, x2), term)).doit())
>>> pdeterm
i*x1**(i - 2)*x2**j*(i - 1)*a[i, j] - j*x1**i*x2**(j - 2)*(j - 1)*a[i, j]

The PDE being identically zero means each coefficient of each x1, x2 term is 0.

>>> pdeterm.coeff(x1**i*x2**(j - 2))
-j*(j - 1)*a[i, j]
>>> pdeterm.coeff(x1**(i - 2)*x2**j)
i*(i - 1)*a[i, j]

This is the same as what you had above if you shift i and j

>>> pdeterm.coeff(x1**i*x2**(j - 2)).subs({j: j + 1})
-j*(j + 1)*a[i, j + 1]
>>> pdeterm.coeff(x1**(i - 2)*x2**j).subs({i: i + 2})
(i + 1)*(i + 2)*a[i + 2, j]

I'm not sure if there's an advantage to having them one way or another.  For a general PDE, you'd want to write a function that does this automatically.

The boundary conditions can be managed in a similar way using subs.

You can then solve the system analytically with solve or numerically with nsolve.


Red black tree partition to $\sqrt{n}$ trees

For question B) you need to make $O(\sqrt{n})$ RB trees from $n$ nodes (there is no tree to start with just bunch of nodes). Thus you need to process each node at least once. Thus time complexity of this building should be $\Omega(n)$. Thus I think there is no hope of getting the $O(\sqrt{n}\log n)$ bound.


Maximum bipartite matching with extra reward for covering certain sets

Let Y131P be "your problem with [weights all equal to 1] and

[left-side degrees bounded above by 3] and [right-side degrees all equal to 1]".

I will show hardness of Y131P.

Wikipedia gives two local gadget reductions from 3-SAT to 1-in-at-most-3-SAT.

The longer one induces a locally-computable bijection between

satisfying assignments whose inverse is also locally-computable.

The following is a linear reduction from 1-in-at-most-3-SAT to Y131P:

There is a left-side node for each variable and for each clause.    Each literal corresponds

to a set of  ( 1 + number_of_occurences_of_that_literal_in_the_input )  right-side nodes,

one of which is labeled with the literal LIT and the others of which are labeled  $\langle$LIT,C$\rangle$  for the

constraints C in which they appear.    Each right-side node labeled with a literal is adjacent

to the left-side node labeled with that literal's variable, and each right-side node labeled

with a pair  $\langle$LIT,C$\rangle$  is adjacent to the left-side node that corresponds to the constraint C.

(A satisfying assignment induces a matching which uses every left-side node and number_of_variables sets, so its value is    # left-side edges  +  number of variables    .

Since the graph is bipartite, no matching can have more edges than the number of left-side nodes.

Due to the left-side variables, sets for complementary literals can't simultaneously be chosen.  Thus, no matchings have value greater than    # left-side edges  +  number of variables  ,

and since the constraints are Exactly-1, there is an efficiently-computable bijection

[between [matchings whose value is that sum] and satisfying assignments]

whose inverse is also efficiently computable.)

In particular, Y131P is FNP-hard.

By [that reduction being linear] and the sparsification lemma, one gets that a

strong version of ETH would imply that Y131P takes takes 2Ω(|E|) time to decide.

Since Y131P can be efficiently padded without changing k (just throw in

isolated edges between new vertices), the same strengthened ETH assumption

would imply that Y131P algorithms' runtime's dependency on k must be 2Ω(k).

The rest of this answer's results apply even when the weights are

given in unary and are equal to each other (but not necessarily to 1).

As I'll use the phrase, "threshold constraints" specify [a multi-set of literals] and

[a positive integer (the "threshold") that's at most the constraint's "size"], where its "size"

is the sum of the multiplicities of the literals in the multi-set.  The constraint is satisfied

if and only if the sum of the multiplicities of the true literals is at least the threshold.

The following is a reduction from [satisfying a list of threshold constraints] to

your problem such that [the number of sets is twice the number of variables] and

[the degree of the left-side nodes are at most  max ( 2 , size_of_largest_constraint ) ]

and the degree of each right-side node is at most

max  (  1  ,  [the maximum, taken over the constraints, of size minus threshold]  )    :

Each variable corresponds to one left-side node and each constraint corresponds

to  ( size_of_the_constraint - the_constraint's_threshold )  left-side nodes.

Each literal corresponds to a set of

( 1 + number_of_occurences_of_its_complement_in_the_input )

right-side nodes, one of which is labeled with the literal LIT and the others of which

are labeled  $\langle$LIT,C$\rangle$  for each occurrence of LIT's complement in a constraint C.

For each constraint C, for each literal LIT whose complement is in C, the node labeled

$\langle$LIT,C$\rangle$  is adjacent to [the left-side nodes that correspond to C] and nothing else.

For each variable v, [the 2 right-side nodes labeled with v's literals] are

adjacent to [the left-side node that corresponds to v] and nothing else.

The weights are equal to each other and greater than the number of variables plus

[the sum, taken over the variables, of the maximum, taken over the variable's

positive and negative literal, of the number of occurrences of that literal in the input].

(Due the the left-side variables, one can't choose both a variable and its negation.

Due to the number of nodes corresponding to a given constraint, one can't

choose too many literals in that constraint to be false, but can do anything else.

The weights are equal and large-enough to dominate over the other part of the matchings' values.

Thus, there's a many-one correspondence between [solutions to the outputted instance of your problem] and [solutions to the input problem], although the output problem can easily have

more than one solution even when the constraint satisfaction problem has a unique solution.)

Since threshold constraints can implement clauses by letting the thresholds be 1,

it follows that if $\big[$there is a real number c such that  c < 1/2  and there are arbitrarily-large

integers d such that for all integers b, there is an algorithm for [$\hspace{.02 in}$your problem with [$\hspace{.02 in}$left-side nodes

having degree d$\hspace{.02 in}$] and [right-side nodes having degree d-1] and  |E| < b$\cdot \hspace{-0.02 in}$k ]  whose runtime is

not eventually bounded below by  2$\hspace{.02 in}$c$\hspace{.02 in}\cdot \hspace{-0.02 in}$k $\big]$   then the corresponding strengthing of SETH is false.

For the same reason, high-power compression of the graph and/or the sets

would yield compression of [threshold-constraint]-SAT, and I'm

not aware of any feasibility results regarding such compression.

(Reminder:  Threshold constraints can implement clauses by letting the thresholds be 1.)

However, that does not say anything about compressing the weights, and independently:

Weighted set packing reduces to maximum-weight independent set with number of vertices equal to the number of sets (adjacent if and only if intersect).  Maximum-weight independent set reduces to your problem (incidence graph).  When the right-side nodes each have degree at most 1, your problem reduces to weighted set packing with the number of sets equal to the number of vertices.

(Remove sets with degree-zero nodes, remove sets with a pair of nodes adjacent to the same node, then replace each set with the set of left-side nodes adjacent to an element of the set

and weight those sets by the original sets' weight plus number of non-removed elements.)

Thus, when the right-side nodes each have degree at most 1, your problem can be

somewhat kernelized.  (That "somewhat kernelization" doesn't simplify the weights.)


Party optimization: maximum weight independent set in a tree/graph

You can interpret a graph problem in whatever way you wish. Note that your interpretation makes sense only for bipartite graphs.

Maximum independent set, even with all weights the same, is (almost) NP-hard to approximate within a factor of $n^{1-\epsilon}$ for any fixed $\epsilon > 0$ (here $n$ is the number of vertices); the actual hardness assumption is NP$\not\subseteq$BPP rather than P$\neq$NP (see for example Anupam Gupta's lecture notes). Under the exponential time hypothesis, any $r$-approximation algorithm must run in at least $2^{n^{1-\epsilon}/r^{1+\epsilon}}$ for any $\epsilon > 0$ (see Chalermsook, Laekhanukit and Nanongkai).


Minimum Length Hamiltonian Path Pair in O(n^2) or better

Since you said a $O(n^2)$ time algorithm would still be useful, there is a straightforward dynamic programming algorithm that runs in time $O(n^2)$.

In particular, a subproblem is specified by a pair of points $(A',P')$; the problem is to find the best pair of paths from $A' \to B$ and $P' \to Q$, using only points that are to the right of both $A'$ and $P'$.  To solve each subproblem, you only have to look at the solution to two subproblems: in particular, to $(Z,P')$ and $(A',Z)$, where $Z$ is the point immediately to the left of the rightmost of $A',P'$.  Therefore, each subproblem can be solved in $O(1)$ time.  As there are $O(n^2)$ subproblems, the $O(n^2)$ running time follows immediately.


Prove: possible to construct automata accepting all strings of other automata sans 1-length strings

Basically, the answer is what @Shaull says in the comments: construct a product automaton with the one that accepts all strings of length unequal 1.
What we use here is the fact that regular languages are closed under intersection. The product construction takes two automata, and simulates them in parallel. States are pairs of states of the original two automata. The combination accepts if both components accept.

But you ask for "minimal operations". So, have a look at what is in fact the automaton that accepts strings of length not 1. It simply has three states "zero", "one" and "many" with a loop for each letter at the last state. It simply counts letters up to length two (and then keeps in that state).

The product construction for this specific automaton is rather straightforward. Set aside a copy of your original automaton $A$. (You might add label "many" to each of the states, but that is extra.) Now add to these fresh copies of the original initial state and all states reachable in one step from the initial state. If the initial state has a loop, it is copied twice. (If you fancy it these get extra labels "zero" and "one"). Now remove final states from the "one"s and copy the original wiring.

Like I said, this is just a particular case of the product construction. In fact it might be even what is in your own pseudo code.


Does it make sense to have both the concept of 'null' and 'Maybe'?

The null value as a default present everywhere is just a really broken idea, so forget about that.

You should always have exactly the concept that best describes your actual data. If you need a type which indicates "unkown", "nothing", and "value", you should have precisely that. But if it does not fit your actual needs then you should not do it. It is a good idea to see what other people use and what they have proposed, but you do not have to follow them blindly.

People who design standard libraries try to guess common usage patterns, and they usually do it well, but if there's a specific thing you need, you should define it yourself. For instance, in Haskell, you could define:

data UnknownNothing a =
     Unknown
   | Nothing
   | Value a

It may even be the case that you should be using something more descriptive that is easier to remember:

data UserInput a =
     Unknown
   | NotGiven
   | Answer a

You could define 10 such types to be used for different scenarios. The drawback is that you won't have available pre-existing library functions (such as those of Maybe), but this usually turns out to be a detail. It's not that hard to add your own functionality.


A related, but different problem is Independent Set: it asks for a set of $k$ vertices that hits each edge at most once (instead of at least once).

A simple reduction from 3-SAT to Independent Set is as follows:

For each clause, we take a clique on $3$ vertices (i.e., a triangle). Each vertex of this triangle corresponds to specific literal appearing in a clause. E.g., a clause $(x_1\vee \neg x_2 \vee x_3)$ would have vertices corresponding to literals $x_1,\neg x_2,x_3$.
Whenever two vertices correspond to conflicting literals, we make those vertices adjacent. E.g., all vertices corresponding to $x_1$ are made adjacent to all vertices corresponding to $\neg x_1$.

We now ask whether an independent set of size $m$ (the number of clauses) exists.

Note that since there is a partition of the graph into $m$ cliques (created in step 1), the size of a maximum independent set is at most $m$ (one vertex from each clique). If there is an independent set of size $m$, then there is a satisfying assignment: such an independent set much select exactly one vertex from each clique, and which vertex is selected tells us which variable is used to satisfy that clause. This gives a satisfying assignment because the edges added in step 2 ensure that no conflicting literals are selected. Conversely, it is easy to see how a satisfying assignment corresponds to an independent set of size $m$.

This reduction should give you a good idea of how to approach the case for Vertex Cover (but this will require some slight modifications).


First-time and second-time seen edges in DFS on undirected graphs

Here is the simplest example.
Let the graph contain two vertices, $x$ and $y$ with one edge $\{x,y\}$. Here is a run of the algorithm.

$x$ and $y$ are marked as "undiscovered".
$y$ is marked as "discovered" and enqueued.
$y$ is dequeued.

Since $x$ is adjacent to $y$ and $x$ is "undiscovered", $x$ is marked as "discovered" and enqueued.
All vertices adjacent to $y$ have been "discovered", so $y$ is marked as
"processed".

$x$ is dequeued.

$y$ is adjacent to $x$ but $y$ is not "undiscovered", do nothing.
All vertices adjacent to $x$ have been "discovered", so $x$ is marked as "processed".

The queue is empty. Done.

You can note that, at step 4.1 when $y$ has been marked as "processed", we are seeing y again by the same edge $\{x, y\}$.

Here is an exercise that characterizes such occasions.
Exercise. Suppose we are given a BFS or DFS of a connected undirected graph with more than one vertices.  Let $y$ be a vertex. Show the following two propositions are equivalent.

There is a time that $y$ was seen again when $y$ had been marked as "processed".
$y$ is not a leaf of the search tree.


Finding recurrence relations for dynamic programming algorithms

If all of your values start out unstored, then $T(n) = n + T(1) + T(2) + \cdots + T(n - 1)$ still, however, when computing $T(n - 1)$, $T(1)$ through $T(n - 2)$ have already been found, so $T(n - 1) = n - 1 + O(1)$. Same for $T(1)$ through $T(n - 2)$ ($T(1)$ is just $O(1)$). This gives an overall runtime of
$$T(n) = n + O(1) + (1 + O(1)) + \cdots + (n - 1 + O(1)) = \frac{n(n-1)}{2}+n(1+O(1))=O(n^2)$$


Why is it meaningless to say the runtime of an algorithm is at least in the order of n squared?

First of all, both sentences are a slight abuse of notation. $\mathcal{O}(n^2)$ and $\Theta(n^2)$ are sets; strictly speaking you can't compare a running time with a set. Saying "$f$ is $\mathcal{O}(g(n))$" is actually a shorthand for "$f$ belongs to the set $\mathcal{O}(g(n))$"; with that in mind, we can rephrase the statements you quote as follows:

  The running time of $A$ is at least $f(n)$ for some $f \in \mathcal{O}(n^2)$.

and:

  The worst-case running time of $A$ is at least $f(n)$ for some $f \in \Omega(n^2)$.

Put in this form, the first statement is well-defined, but it's not really insightful. In fact, it is always true. Let $g$ be the constant function $0$. Certainly $g$ is a member of $\mathcal{O}(n^2)$, and whatever the running time of $A$ is on input of size $n$, it is at least $g(n)$.

Intuitively speaking, big-oh is an upper bound: if I tell you: "I have at least $100 or less", I didn't really give you any information at all.

On the other hand, the second statement guarantees that the worst-case running time of $A$ cannot be too low: it must grow at least quadratically.


Edit: My answer was based on assuming the code given as a pseudo-code, rather than a concrete Python example. For Python, the data structure is a dictionary (hash map) and so finding neighbors (the in) operation will in fact be $O(1)$ on average, giving $\Theta(n^2)$ overall complexity on average for both graphs. Rare worst cases in hash maps can depend on implementation. In general for pseudo-codes, see my original answer below.

The complexity also depends on the data structure being used for storing the graph $G$. If an adjacency list is used, where for every vertex $v$ in the graph, its neighbors are stored in an array/linked list, then the above complexities are valid. Here's how:

For the central node of the star graph, there are $n-1$ neighboring vertices. Then, the pair of neighbors of this central node - the $w$ and $u$ vertices - can be selected in $\Theta(n^2)$ ways. For each such $w$, checking if $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, since each such $w$ only has $1$ neighbor - the central node $v$. This gives overall complexity of $\Theta(n^2)$.

For a clique of size $n$, every node has $\Theta(n)$ neighbors. Then, the pair of neighbors $w$ and $u$ for any node $v$ can be chosen in $\Theta(n^2)$ ways - this is the complexity of the two outer for loops. For every such $w$, checking if $u$ is its neighbor requires going through the list of $\Theta(n)$ neighbors of $w$, and so the if statement has $\Theta(n)$ complexity. This takes the overall complexity of the two nested for loops and the if loop to $\Theta(n^3)$.

However, there are other representations of the graph data structure, which give different (generally better) complexities for the same algorithm. For example, having an adjacency matrix to represent the graph means that the check for $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, even for a clique. Similarly, using a hash set instead of list/array to store neighbors would mean checking for neighbors can be done in $\Theta(1)$ on average. These are the more common representation. You could also choose an arbitrary representation where neighbors are sorted (just to demonstrate how the underlying data structure can affect algorithm complexity). In such a case, checking for neighbors will take $\Theta(\log n)$, giving overall $\Theta(n^2 \log n)$. Each has its pros and cons, and the appropriate data structure must be chosen according to your situation.


Variant of greedy algorithm for vertex cover

No, this is a terrible algorithm. Consider a star graph: the vertices are $x,y_1,\ldots,y_n$, and the edges are $(x,y_1),\ldots,(x,y_n)$. Your algorithm goes over the edges in an arbitrary order, and always picks the $y$ vertices. It ends up with $n$ vertices rather than the optimal $1$ vertex solution.


Efficiency/Redundancy in Chomsky normal form

Both grammars are in CNF. One of the possible rule formats for CNF is $A \to BC$, where $A$, $B$, and $C$ are non-terminals, but it is not necessary for them to be different from another. Hence, in your case, $S \to AA$ is also a valid rule for CNF.

I should add CNF has nothing to do with an "efficient" way to write a grammar (however you should define that; if you simply mean the description is shorter, then counterexamples abound). Rather, CNF is useful when employing techniques such as the CYK algorithm.


Hint: $\mathrm{gcd}(a,b) = b$ iff $b|a$. Since you're only looking for pairs in which $a \leq b$, this forces $a = b$.


What is an instance of NP complete problem?

Other answers are good, I'll give only another trivial example:

problem: "given two numbers $k,n$ with $1 < k < n$, does a number $m$ smaller or equal than $k$ exist such that $n$ is divisible by $m$ ?"
the instances of the problem (or informally the input of the problem) are all the valid pairs $(k,n)$ such that $1 < k < n$; so $I = \{ (2,3),(2,4),...,(3,4),(3,5),...\}$
the set of solutions is the set $S = \{ YES, NO \}$, indeed the problem is a decision problem (the answer to the question "does exist ...?" is simply YES or NO)
the abstract problem $Q$ is a subset of $I \times S$ and is the relation that associates an instance of the problem to the correct answer

So:

Q = { ( (2,3), NO  ),
      ( (2,4), YES ),
      ( (2,5), NO  ),
      ....
      ( (6,13), NO ),
      ( (6,14), YES ),
      ...
      ( (7,13), NO ),
      ( (7,14), YES ),
      ...
    }

P.S. the problem $Q$ is known as INTEGER FACTORIZATION and probably you'll meet it again ... :)


Complement of language $\{ x \in \{a,b,c,d\}^* : \exists$ prefix $y$ of $x$ such that $||y|_a - |y|_b|\leq 10 \}$

First of all, a language is regular iff its complement is regular. Therefore it suffices to determine whether $L$ itself is regular.

Indeed, since $\epsilon$ is a prefix of every word, and $\epsilon$ satisfies $||\epsilon|_a-|\epsilon|_b| \leq 10$, we see that $L = \Sigma^*$, and in particular $L$ is regular.

Matters become more interesting if we replace the condition $||y|_a-|y|_b| \leq 10$ by its complement $||y|_a-|y|_b| > 10$. In this case the language $L$ is still regular, but the argument is a bit more complicated. Let us show that the following language is regular:
$$
L' = \{ x \in \{a,b,c,d\}^* : \text{some prefix $y$ of $x$ satisfies $||y|_a-|y|_b| > 10$}\}.
$$
(Its complement is the language of all words, all of whose prefixes satisfy $||y|_a-|y|_b| \leq 10$.)

We construct a DFA with 22 states $\{q_{-10},\ldots,q_{+10},q_f\}$. The initial state is $q_0$, and the unique final state is $q_f$. The transition function is given by the following table:
$$
\begin{array}{c|cccc}
q & \delta(q,a) & \delta(q,b) & \delta(q,c) & \delta(q,d) \\\hline
q_{-10} & q_{-9} & q_f & q_{-10} & q_{-10} \\
q_{-9} & q_{-8} & q_{-10} & q_{-9} & q_{-9} \\
\vdots & \vdots & \vdots & \vdots & \vdots \\
q_9 & q_{10} & q_8 & q_9 & q_9 \\
q_{10} & q_f & q_9 & q_{10} & q_{10} \\
q_f & q_f & q_f & q_f & q_f
\end{array}
$$
If the current prefix satisfies $||y|_a-|y|_b| > 10$, the DFA moves to state $q_f$ and stays there. Otherwise, the DFA is in state $q_i$, where $i = |y|_a - |y|_b$.


Yes, B-trees and B+ trees can be used to create a sorted array or other ordered data structure.

There is no one data structure that we can call "optimal".  There are a variety of data structures that have various tradeoffs.  Their performance has some similarities, and which one you choose depends on the specific situation (whether you want an in-memory data structure or an on-disk data structure, how important ease of programming is, how important worst-case vs average-case performance is, and many other considerations).  So, I would be reluctant to pick any one of them as "optimal".


Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done.
$\newcommand{\lang}[1]{\mathcal{L}(#1)}
 \newcommand{\sent}[1]{\vartheta(#1)}
 \newcommand{\derive}{\mathbin{\Rightarrow}}
 \newcommand{\derivestar}{\mathbin{\Rightarrow^*}}
 \newcommand{\nats}{\mathbb{N}}$

The basic idea is to not restrict oneself to words of grammar and language; it is hard to grasp the structure of the grammar in this way. Instead, we will argue about the set of sentences the grammar can create. Furthermore, we will split one daunting proof goal into many small goals that are more tractable.

Let $G=(N,T,\delta,S)$ a formal grammar with non-terminals $N$, terminals $T$, rules $\delta$ and starting symbol $S \in N$. We
denote by $\sent{G}$ the set of sentences that can be derived from $S$ given $\delta$, that is $\alpha \in \sent{G} \iff S \derivestar \alpha$. The language generated by $G$ is $\lang{G} = \sent{G} \cap T^*$. Suppose we want to show that $L = \lang{G}$ for some $L \subseteq T^*$.

The ansatz

Here is how we go about that. We define $M_1, \dots, M_k \subseteq (N \cup T)^*$ so that

$\displaystyle \sent{G} = \bigcup_{i=1}^k M_i$ and
$\displaystyle T^* \cap \bigcup_{i=1}^k M_i = L$.

While 2. is usually clear by definition of the $M_i$, 1. requires some serious work. The two items together clearly imply $\lang{G} = L$ as desired.

For ease of notation, let's denote $M = \bigcup_{i=1}^k M_i$.

The rocky road

There are two major steps to performing such a proof.

How to find (good) $M_i$?
One strategy is to investigate phases the grammar works through. Not every grammar is amenable to this idea; in general,
this is a creative step. It helps if we can define the grammar ourselves; with some experience, we will be able to define
grammars more tractable with this approach.
How to prove 1.?
As with any set equality, there are two directions.

$\sent{G} \subseteq M$: (structural) induction over the productions of $G$.
$M \subseteq \sent{G}$: Usually one induction by $M_i$, starting from the one that contains $S$.

This is as specific as it gets; the details depend on the grammar and language at hand.

Example

Consider the language

$\qquad \displaystyle L = \{ a^n b^n c^m \mid n,m \in \nats \}$

and the grammar $G = (\{S,A\}, \{a,b,c\}, \delta, S)$ with $\delta$ given by

$\qquad \begin{align}
  S &\to Sc \mid A \\
  A &\to aAb \mid \varepsilon
\end{align}$

for which we want to show that $L = \lang{G}$. What are the phases this grammar works through? Well, first it generates $c^m$ and then $a^n b^n$. This immediately informs our choice of $M_i$, namely

$\qquad \begin{align}
  M_0 &= \{Sc^m \mid m \in \nats \} \;, \\
  M_1 &= \{ a^n A b^n c^m \mid m,n \in \nats \} \;, \\
  M_2 &= \{ a^n b^n c^m \mid m,n \in \nats \} \;. \\
\end{align}$

As $M_2 = L$ and $M_0 \cap T^* = M_1 \cap T^* = \emptyset$, item 2. is already taken care of. Towards 1., we split the proof in two parts as announced.

$\mathbf{\sent{G} \subseteq M}$

We perform structural induction along the rules of $G$.

I.A.: Since $S = Sc^0 \in M_0$ we anchor successfully.

I.H.: Assume for some set of sentences $X \subseteq \sent{G}$ that we also know $X \subseteq M$.

I.S.: Let $\alpha \in X \subseteq \sent{G} \cap M$ arbitrary. We have to show that whatever form $\alpha$ has and whatever rule is applied next, we don't leave $M$. We do this by complete case distinction. By induction hypothesis, we know that (exactly) one of the following cases applies:

$w \in M_0$, that is $w = Sc^m$ for some $m \in \nats$.
Two rules can be applied, both of which derive a sentence in $M$:

$Sc^m \derive Sc^{m+1} \in M_0$ and
$Sc^m \derive Ac^m = a^0Ab^0c^m \in M_1$.

$w \in M_1$, i.e. $w = a^nAb^nc^m$ for some $m,n \in \nats$:

$w \derive a^{n+1}Ab^{n+1}c^m \in M_1$ and
$w \derive a^nb^nc^m \in M_2$.

$w \in M_3$: since $w \in T^*$, no further derivations are possible.

Since we have successfully covered all cases, the induction is complete.

$\mathbf{\sent{G} \supseteq M}$

We perform one (simple) proof per $M_i$. Note how we chain the proofs so "later" $M_i$ can anchor using the "earlier" $M_i$.

$M_1$: We perform an induction over $m$, anchoring in $Sc^0 = S$ and using $S \to Sc$ in the step.
$M_2$: We fix $m$ to an arbitrary value and induce over $n$. We anchor in $Ac^m$, using that $S \derivestar Sc^m \derive Ac^m$ by the former proof. The step progresses via $A \to aAb$.
$M_3$: For arbitrary $m,n \in \nats$ we use the former proof for $S \derivestar a^nAb^nc^m \derive a^nb^nc^m$.

This concludes the second direction of the proof of 1., and we are done.

We can see that we heavily exploit that the grammar is linear. For non-linear grammars, we need $M_i$ with more than one variable parameter (in the proof(s)), which can become ugly. If we have control over the grammar, this teaches us to keep it simple. Consider as deterring example this grammar which is equivalent to $G$:

$\qquad \begin{align}
  S &\to aAbC \mid \varepsilon \\
  A &\to aAb \mid \varepsilon \\
  C &\to cC \mid \varepsilon
\end{align}$

Exercise

Give a grammar for

$\qquad L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \nats, k \neq o, 2l = n, m \geq 2 \}$

and prove its correctness.

If you have trouble, a grammar:

   Consider $G = (\{S,B_r,B_l,A,C\}, \{a,b,c\}, \delta, S)$ with productions

 $\quad \begin{align} S   &\to bSb \mid B_l \mid B_r \\     B_l &\to bB_l \mid bA \\     B_r &\to B_r b \mid Ab \\     A   &\to aAaa \mid C \\     C   &\to bcC \mid bcbc   \end{align}$

and $M_i$:

   $\quad\begin{align}     M_0 &= \{ b^i S b^i \mid i \in \nats \} \\     M_1 &= \{ b^i B_l b^o \mid o \in \nats, i \geq o \} \\     M_2 &= \{ b^k B_r b^i \mid k \in \nats, i \geq k \} \\     M_3 &= \{ b^k a^i A a^{2i} b^o \mid k,o,i \in \nats, k \neq o \} \\     M_4 &= \{ b^k a^l (bc)^i C a^{2l} b^o \mid k,o,l,i \in \nats, k \neq o \} \\     M_5 &= L   \end{align}$

What about non-linear grammars?

The characterising feature of the class of context-free languages is the Dyck language: essentially, every context-free language can be expressed as the intersection of a Dyck language and a regular language. Unfortunately, the Dyck language is not linear, that is we can give no grammar that is inherently suited to this approach.

We can, of course, still define $M_i$ and do the proof, but it's bound to be more arduous with nested inductions and what not.
There is one general way I know of that can help to some extent. We change the ansatz to showing that we generate at least all
required words, and that we generate the right amount of words (per length). Formally, we show that

$\displaystyle \sent{G} \supseteq L$ and
$\displaystyle |\lang{G} \cap T^n| = |L \cap T^n|$ for all $n \in \nats$.

This way, we can restrict ourselves to the "easy" direction from the original ansatz and exploit structure in the language, ignoring overcomplicated features the grammar may have. Of course, there is no free lunch: we get the all new task of counting the words $G$ generates for each $n \in \nats$. Lucky for us, this is often tractable; see here and here for details¹. You can find some examples in my bachelor thesis.

For ambiguous and non-context-free grammars, I'm afraid we are back to ansatz one and thinking caps.

When using that particular method for counting, we get as a bonus that the grammar is unambiguous. In turn, this also means that the technique has to fail for ambiguous grammars as we can never prove 2.


Understanding the closed form derivation on the function f(n/3) + n^2 +3

The real question is where $\left(\frac{n}{3}\right)^3$ comes form. If you look at the formula, you see that it really should have been $\left(\frac{n}{3^2}\right)^2$.

The morale here is that people make mistakes. Calculations you see in tutorial, in lecture notes, and even in textbooks, are not infallible. When something seems to be amiss, try to understand what calculation is being done, and then try to reproduce it on your own. The mistake may disappear, as in this case, or may persist, in which case there might be a more serious issue in the mathematical development; unfortunately, this also sometimes happens. We are only humans, after all.


reduction from SET-COVER to VERTEX-COVER

No, since  {{0,1},{1}}  and  {{0,1},{1,2}}  yield isomorphic graphs

but the sizes of their minimum set covers are different.


Log space reduction from STCONN to CYCLE

There is no need to store the new graph on the tape. We just need to be able to output it in logspace. This is straightforward, for any reasonable encoding of graphs.


Correct nomenclature: Hamilton path, Hamilton's path or Hamiltonian path?

I have seen both Hamilton path (or Hamilton cycle) and Hamiltonian path (or Hamiltonian cycle). A graph, however, is always Hamiltonian (if it contains a Hamilton/Hamiltonian cycle). Consider for example the titles of two papers: Hamiltonian cycles in random regular graphs (Fenner & Frieze) and Generating and counting Hamilton cycles in random regular graphs (Frieze, Jerrum, Molloy, Robinson & Wormald). Alan Frieze apparently doesn't care too strongly about the issue.

However, I've never seen Hamilton's path or cycle.


Express a "complex" IF-Statement to Linear Programming

You can solve this by introducing some temporary variables ($t,u,v$) and applying the big-M method.

For each expression L <= b <= U, we'll introduce 0-or-1 variables $t,u,v$, with the intent that $u=1$ if and only if $L \le b$ holds, $v=1$ if and only if $b \le U$ holds, and $t=1$ if and only if $L \le b \le U$ holds.  We'll enforce this with the inequalities

$$L \le b + M(1-u), L > b - Mu, b \le U + M(1-v), b > U - Mv, 0 \le u+v - 2t \le 1,$$

where $M$ is a sufficiently large constant (you can take it to be at least the largest possible value of $b$, and at least $L$ and at least $U$).  How does this work?  The first two inequalities define $u$ so that $u=1 \Leftrightarrow (L \le b)$ using the technique from Boolean variable true iff equation is satisfied in ILP.  The next two inequalities define $v$, similarly.  The last inequality ensures that $t$ is the logical-AND of $u$ and $v$, using the technique from https://cs.stackexchange.com/a/43884/755.

Now, we'll enforce the constraint if t=1 then z = k*c for some constant c.  We can enforce this using the inequalities

$$ck - M(1-t) \le z \le ck + M(1-t)$$

where $M$ is a sufficiently large constant (in particular, it needs to be at least $c$ times the largest possible value of $k$, and at least the largest possible value of $z$).  Why does this do what we want?  The argument is similar.  If $t=1$, then the inequality is equivalent to $ck \le z \le ck$, which implies $ck=z$; if $t=0$, the inequality is equivalent to $ck-M \le z \le ck+M$, which imposes no restrictions on $z$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for more techniques for handling other sorts of inequalities.


Assumptions when selecting an algorithm or data structure

You can categorize data structures by their need of memory or processing power. Each rated for writing or reading purpose. Some data structures are optimized for searching, some only for fast storing.

Ask yourself how many data you're going to store.
If it's a lot, you have to choose the right algorithm, if not it doesn't really matter.

Another question could be, do you need a growing data structure or just a ring buffer for example.

Regarding data manipulation with algorithms, there is a bunch of considerations to make.
With growing data, how much does memory usage, processing power, external storage capacity and access times grow?
The big O notation would be a term to refer to.
Here too, it's important if your 'manipulation' is reading, searching or writing?

You will find an algorithm or a data structure out there for every use case.


You seem to be confusing languages and strings.

An algorithm that decides a language $L$ is an algorithm whose input is a string $w$ and whose output is true if $w\in L$ and false if $w\notin L$.  As such, an algorithm can only decide one language: specifically, the language
$$L_A = \{w\mid A(w)=\mathrm{true}\}\,.$$

So, when you say, "then $A$ would decide all $L$", you're making a category error. An algorithm cannot possibly decide more than one language. What you've described is an algorithm that outputs true for every input: in other worse, an algorithm that decides the language $\{0,1\}^*$.

Note that $A$ decides a language by taking strings as inputs; it doesn't take languages as input and decide whether that langauge is in P.


Shortest paths in weighted graphs, and minimum spanning trees

Let's consider the hypothesis of the question to try clarify every aspect:

Our Graph G should:

be undirected
be weighted
be connected
with no negative weights
with all weights distinct
in this graph, the shortest path between any two vertices is on the
minimum spanning tree (MST)

I believe the key point here is the article used in point 6, as pointed out by David Richerby comment

From the wikipedia page: Article (grammar):

Definite Article

  A definite article indicates that its noun is a particular one (or
  ones) identifiable to the listener. It may be something that the
  speaker has already mentioned, or it may be something uniquely
  specified. The definite article in English, for both singular and
  plural nouns, is the.

Indefinite article

  An indefinite article indicates that its noun is not a particular one
  (or ones) identifiable to the listener. It may be something that the
  speaker is mentioning for the first time, or its precise identity may
  be irrelevant or hypothetical, or the speaker may be making a general
  statement about any such thing.

So point 6 lends to some ambiguity:

It could be that the shortest path is implied to be unique. (In
this case I must say the hypothesis and the question are sort of
misleading)
Or it could be that the shortest path is only one of the
possible shortest paths between any two vertices

So if we interpret the hypothesis as per point 1 (i.e. the shortest path means there is a unique shortest path) then the hypothesis is also the answer.

If we interpret the hypothesis as per point 2 then we could consider the following undirected graph:

A--5--B
|   /
2  3
| /
 C

There is no unique shortest path between A and B
Since we could have both:
AB (cost 5)
AC + CB (cost 2+3 = 5)

So if we interpret the hypothesis not meaning the shortest path is unique and asks you to verify this, then we have demonstrated that there is such graph with no unique shortest path that satisfies all other conditions.


Confusion in Turings proof of the undecidability of the Entscheidungsproblem

The transliteration of the passage into modern langauge would go as follows.
We extend the language of first-order Peano arithmetic with a unary predicate $G$ (and no axioms for $G$).
For a number $n \in \mathbb{N}$, let $\overline{n}$ be the numeral
$$\underbrace{S(S(\cdots S}_{n}(0)))$$
where $S$ is the successor symbol. For example, $\overline{3} = S(S(S(0))$.
Consider a formula $\mathfrak{U}(x)$ written in this language, whose only free variable is $x$ such that, for every $n \in \mathbb{N}$:

Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow G(\overline{n})$, or
Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow \lnot G(\overline{n})$.
Peano axioms do not prove $\lnot \mathfrak{U}(\overline{n})$.

Define $\alpha : \mathbb{N} \to \{0,1\}$ by
$$\alpha(n) =
\begin{cases}
1 & \text{if Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow G(\overline{n})$},\\
0 & \text{if Peano axioms prove $\mathfrak{U}(\overline{n}) \Rightarrow \lnot G(\overline{n})$.}
\end{cases}
$$
We say that $\mathfrak{U}$ defines the sequence $\alpha$.
Intuitively, we think of $G(x)$ as stating "the $x$-th digit of $\alpha$ is $1$", and of $\lnot G(x)$ as stating "the $x$-th digits of $\alpha$ is $0$".
The first and second condition on $\mathfrak{U}$ ensure that $\mathfrak{U}$ always assigns $\alpha(n)$ the value $0$ or the value $1$.
The third condition ensures that $\mathfrak{U}$ never assigns both $0$ and $1$ to $\alpha(n)$ (because it follows from the first two conditions that $\lnot \mathfrak{U}(\overline{n})$ is equiprovable with $G(\overline{n}) \land \lnot G(\overline{n})$).
Example: The formula $G(x)$ defines the sequence $1, 1, 1, 1, 1, \ldots$.
Example: The formula $G(S(x))$ does not define a sequence because $G(S(0)))$ does not imply $G(0)$ and it does not imply $\lnot G(0)$. (Remember that $G$ is a primitive symbol and that we have no axioms about it.)
Example: The formula $G(0) \land \forall x \,.\, \lnot G(S(x))$ defines the sequence $1, 0, 0, 0, 0, \ldots$
Example: The formula $x \neq 0 \land \Rightarrow G(x)$ does not define the sequence because Peano axioms prove $\lnot (0 \neq 0 \land G(0)$, thus the third condition is violated. If we tried to use this formula to define a sequence, it would assign $0$ and $1$ to $\alpha(0)$ (and it would assign $1$ to all other terms of $\alpha$).
Example: The formula $G(0) \land \lnot G(S(0)) \land \forall x . G(S(S(x)))$ defines the sequence $1, 0, 1, 1, 1, 1, \ldots$
Example: The formula
$$((\exists y . x = 2 \cdot y) \Rightarrow G(x)) \land
  ((\exists y . x = S(2 \cdot y)) \Rightarrow \lnot G(x))
$$
defines the sequence $0, 1, 0, 1, 0, 1, \ldots$


Efficient rasterisation of vector image with polygons

An alternative approach is to use a quad-tree.

One approach is to store each polygon in the deepest node that corresponds to a region that wholly contains the polygon.  Given a test point, you traverse the quad-tree, and when you visit a node, you do a point-in-polygon test for each polygon associated with that node.  This then lets you do a smaller number of point-in-polygon tests.

An alternative approach is to continue subdividing each region recursively.  Stop subdividing when a region intersects with at most 2 polygons (or replace 2 with any other constant) or when you have hit some maximum depth, mark that as a leaf node, and associate those polygons with the leaf node.  Given a test point, you traverse the quad-tree until you hit a leaf node, then you do a point-in-polygon test for each polygon associated with that leaf node.  This trades space for time: it uses more space (more quad-tree cells) but uses fewer point-in-polygon tests.

It should be straightforward to build either type of quad-tree.

You can think of a quad-tree as a recursive version of your bitmap idea, where the bitmap is stored in a sparse way (large regions of all-white or all-black can often be collapsed to a single node), and where you have an image pyramid of bitmaps.


You are technically correct. A modern practical computer has finitely many states, and so any program it runs will eventually repeat a state.

However, I would like to warn against interpreting this observation in the wrong way. It is not a problem in practice. The number of possible states is huge (it's huuuuuuuuuuuuuuuuuuuuge). Algorithms that are designed for machines with infinite resources (such as Turing machines) typically run just fine on a modern computer. Of course, they may use up all available memory if they are especially memory-intensive, but that's different from them cycling because they somehow repeated a configuration due to computer limitations. And when programs do cycle forever unintentionally, it is not the limited size of the computer that does it, but rather programming errors.

It is more practical to mathematically model modern computers as if they have unlimited memory than to model them as finite-state machines. This situation is a bit like modelling in physics: classical fluid dynamics models a discrete system of atoms as if it were a continuous one.


Why is two-phase commit better than naive master-slave replication?

You are confusing the purpose of the algorithms. The 2PC is a voting algorithm where the two sides have different data and different criteria for choosing a vote. The master-slave is a redundancy algorithm that aims to have identical copies at two places.

Besides, your master-slave is asynchronous where you return to client before replication. The client sees completion but the master can still become irrecoverable before replication, at which point you have data loss. 2PC is not subject to this.

That said, organizations may use 2PC in to implement master-slave, by making the “slave” always vote yes. This is essentially master-slave in synchronous mode, with unnecessary message overhead.

What you want to advocate for is probably synchronous master-slave, where you return to client after the slave confirms. It’s faster than 2PC because you only need one message exchange for each slave, instead of the two exchanges required for 2PC.


Maximizing the Sum of a Subset with Excluding pairs

Your problem is known as maximum-weight independent set (more often, simply maximum independent set). We think of the $x_i$ as vertices in a graph, each constraint corresponding to an edge $(x_i,x_j)$. An independent set is a set of vertices with no edges, which is exactly your condition.

Unfortunately, maximum-weight independent set is NP-complete, and $n^{1-\epsilon}$-hard to approximate (for every $\epsilon>0$) even when all weights are the same.


Algorithm. We maintain a set $S$, which is initially a set of vertices of $X$. Let $CH(S)$ be the convex hull of $S$. We want to find $S$ such that $CH(S) \subset Z$ is a maximal polygon.
We first define operation $extend(s,t)$ which

Finds a point $x$ on the ray starting from $s$ and going through $t$ such that $CH(S \cup \{x\}) \subset Z$ and $x$ is the farthest from $s$ (i.e. it's the most we can extend the polygon in direction $s \to t$).
Add $x$ to $S$.

$extend$ is the only operation we'll use. Therefore, $CH(S) \subset Z$ by construction. We only need to select a sequence of extensions so that $CH(S)$ is maximal.
The algorithm consists of $2$ phases:

Let $c$ be any point strictly inside the $X$. For each vertex $v$ of $Z$ (including inner vertices), perform $extend(c, v)$
For all edges $(u,v)$ of $CH(S)$, while possible, perform $extend(u,v)$ and $extend(v,u)$.

The following example demonstrates the algorithm (I omit steps which don't modify $S$, but we should try all vertices of $Z$ (including holes' vertices) and all edges of $CH(S)$):

Proof of maximality.

Let $x \in Z$ be a point such that $x \in Z \setminus CH(S)$ and $CH(S \cup \{x\}) \subset Z$.
Let $u \in S$ be a vertex s.t. $(u,x)$ is an edge in $CH(S \cup \{x\})$. We can assume that $x$ is arbitrarily close to $u$. It's clear that when $x$ is sufficiently close to $u$, one of two neighbors of $u$ in $CH(S)$ becomes a neighbor of $x$ in $CH(S \cup \{x\})$. We call this neighbor $v$. Let $u'$ be another neighbor of $u$, and $v'$ be another neighbor of $v$.
Since we can't extend $(v', v)$ and $(u',u)$, there must exist a vertex $y$ of polygon $Z$ lying strictly between lines $(v', v)$ and $(u',u)$ (it's cumbersome to explain, but it's kind of obvious). Then line $(c,y)$ either intersects $(u,x)$ or $(v,x)$. Let $z$ be the intersection point. Then this point 1) lies outside of $CH(S)$, 2) lies in $CH(S \cup \{x\})$ and 3) lies on line $(c,y)$. This means that during phase $1$ we didn't fully extend to $y$, contradiction.
Complexity.
We first need to estimate the complexity of $extend$. One can do this with a binary search: for a candidate, build a convex hull and check if it lies inside of $Z$. The convex hull can be built in $O(n)$ (since we only need to add one point) and an intersection with $Z$ can be checked in $O(n)$, so the total time is $O(n \log (precision))$. I suspect that it's possible to get rid of binary search and get $O(n)$ or $O(n \log n)$ time.
Now, we need to estimate the number of calls of $extend$. There are $O(n)$ calls of $extend$ in the first phase.
In the second phase, each time we successfully perform $extend$ (i.e. the area of $CH(S)$ increases), one of two things happen:

A vertex of $CH(S)$ which was not on the boundary of $Z$, now lies on the boundary of $Z$.
A vertex of $Z$ which was not on the boundary of $CH(S)$, now lies on the boundary of $Z$.

Since there are $O(n)$ vertices of $Z$ and $CH(S)$ (it can't have more vertices than $Z$), we call $extend$ at most $O(n)$ times.
Therefore, the total running time is $O(n^2 \log (precision))$


Which calculating running time are correct?

The $T(n)= 2 T(n/2)+O(n)$ is $\mathcal{O}(n \log(n))$

Your recursion $T(n)=T(n/2)+O(n)$ is $\mathcal{O}(n)$ by The 3rd case of The Master Theorem.


Do you have to do reduction both ways to prove a problem is NPC?

The answer by Draconis is wrong in "showing that the new problem is NP-hard." Reducing from something in NP to a new problem does not show NP-hardness. In particular, if a problem A is in P it is also in NP. Suppose there is a reduction from such a polynomial-time solvable A to some new problem B. Then, problem B still can be in P, and in this case B is not NP-hard.
The correct version of this answer says that to show that a new problem is NP-hard one has to reduce from another NP-hard problem A. Then, the new problem cannot be "simpler" than the hardest problem in NP. If it were, then one could solve all NP-hard problems via the new problem, first reducing any problem to A (which is NP-hard by assumption) and then to B.


LRU only applies if the cache is set-associative and you need a hint as to in which set you write new data.  In a direct mapped cache, here is only one place to put data.


Sliding Window Protocol, waiting Time calculation

You have not calculated the $R_{TT}$ you just used the Propagation Time that a frame needs to travel one way of the duplex link.

This is how you calculate the $R_{TT}$:

$R_{TT} =$ [Propagation time for frame] + [Transmission time for frame] + [Propagation time for ACK] + [Transmission time for ACK]

Since ACK is piggybacked we assume that its frame size will also be 1000bits, so the $R_{TT}$ is:

$R_{TT} = 25ms + 1ms + 25ms + 1ms = 52ms $

Therefore waiting time is: $52ms - 32ms = 20ms$