How can we assume that basic operations on numbers take constant time?

For people like me who study algorithms for a living, the 21st-century standard model of computation is the integer RAM.  The model is intended to reflect the behavior of real computers more accurately than the Turing machine model.  Real-world computers process multiple-bit integers in constant time using parallel hardware; not arbitrary integers, but (because word sizes grow steadily over time) not fixed size integers, either.

The model depends on a single parameter $w$, called the word size.  Each memory address holds a single $w$-bit integer, or word.  In this model, the input size $n$ is the number of words in the input, and the running time of an algorithm is the number of operations on words.  Standard arithmetic operations (addition, subtraction, multiplication, integer division, remainder, comparison) and boolean operations (bitwise and, or, xor, shift, rotate) on words require $O(1)$ time by definition.

Formally, the word size $w$ is NOT a constant for purposes of analyzing algorithms in this model.  To make the model consistent with intuition, we require $w \ge \log_2 n$, since otherwise we cannot even store the integer $n$ in a single word.   Nevertheless, for most non-numerical algorithms, the running time is actually independent of $w$, because those algorithms don't care about the underlying binary representation of their input.  Mergesort and heapsort both run in $O(n\log n)$ time; median-of-3-quicksort runs in $O(n^2)$ time in the worst case.  One notable exception is binary radix sort, which runs in $O(nw)$ time.

Setting $w = \Theta(\log n)$ gives us the traditional logarithmic-cost RAM model.  But some integer RAM algorithms are designed for larger word sizes, like the linear-time integer sorting algorithm of Andersson et al., which requires $w = \Omega(\log^{2+\varepsilon} n)$.

For many algorithms that arise in practice, the word size $w$ is simply not an issue, and we can (and do) fall back on the far simpler uniform-cost RAM model.  The only serious difficulty comes from nested multiplication, which can be used to build very large integers very quickly.  If we could perform arithmetic on arbitrary integers in constant time, we could solve any problem in PSPACE in polynomial time.

Update: I should also mention that there are exceptions to the "standard model", like Fürer's integer multiplication algorithm, which uses multitape Turing machines (or equivalently, the "bit RAM"), and most geometric algorithms, which are analyzed in a theoretically clean but idealized "real RAM" model.

Yes, this is a can of worms.


Okay, let's look at what we know about the type of applyTwice, $\alpha$:

It is given two arguments, so $\alpha = \beta_1 \to \beta_2 \to \gamma$, and $f$ has type $\beta\_1$ and $x$ has type $\beta_2$
$f$ is applied to $f$, so $\beta_1 = \beta_1 \to \gamma_2$
$(f\ f)$ is applied to $x$, so $\gamma_2 = \beta_2 \to \gamma$

The kicker here is the second equation, $\beta_1 = \beta_1 \to \gamma_2$. This equation has no finite solution, because $S \to T$ is structurally larger (uses at least one more type constructor) than either $S$ or $T$.

So the only type that satisfies this equation is infinite recursive type $\mu T\ldotp T \to \gamma_2 = ((\ldots \to \gamma\_2) \to \gamma\_2) \to \gamma\_2) \to \gamma\_2) \to \gamma\_2) \to \gamma\_2)$. But this type doesn't really have any meaning in Haskell or related type systems, and it's pretty hard represent an infinite type in finite memory in a concrete form.

Remember that $f\ f$ is giving $f$ as an argument to $f$. If you want to apply $f$ twice, you could use function composition (f . f) x, or $(f \circ f)\ x$ in math notation.


I have trouble translating Turing machine language, can you help me break down language notation to English?

When $s$ is a symbol and $n$ is a natural number, "$s^n$" means "$s$ repeated $n$ times".  So you're being asked to recognize the language of all strings that consist of $n$ zeros followed by $n$ ones, for any possible value of $n\geq 0$.  That is, $\{\epsilon, 01, 0011, 000111, 00001111, \dots\}$, where $\epsilon$ denotes the empty string (some people write $\lambda$ for the empty string, instead).


Which Grows Faster: Factorial or Double Exponentiation

You can find the result by taking a $\log$. Hence:

$$\log(2^{3^n}) = 3^n$$
$$\log(n!) \leqslant \log(n^n) = n\log n$$

(In the latter equation, we have used the fact that $n! \leqslant n^n$, as you note in the question.)

Of course $3^n$ grows faster than $n \log n$.
As $\log$ is an increasing function, we can say $2^{3^{n}}$ grows faster than $n^n$, and also $n!$.


Finding negative cycles for cycle-canceling algorithm

To expand upon my comment, remember, this algorithm for finding Min-Cost-Flow relies on the fact that $f$ is maximal. By first running Ford-Fulkerson to find $f$ and the resulting residual network $G_f$, the cost $f$ is then reduced by finding negative cycles in $G_f$. That is, by finding negative cycles in $G_f$ we do not change the amount of flow, $f$, but merely the cost.

Now by running Bellman-Ford from $t$ in $G_f$ we can trace backwards on edges that have non-negative flow (by definition of $G_f$). If cycles are adjacent to any edges in these paths, then we can "transfer" some amount of flow to other edges in the cycle. In other words, we keep the net-flow for some cycle the same, but are able to change the cost.

Notice an unreachable cycle from $t$ must have zero-flow. Otherwise we would have a contradiction in $f$ being maximal.

I apologize for the "hand-wavy-ness" of this explanation. I will try to be more formal when I have time tonight.


On the hardness of constraint satisfaction

As pointed out by Antti Röyskö the solution $\mathbf{x} = 0$ always maximizes the objective function since  $\sum_{j=1}^n\mathbb{I}[\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0]$ corresponds to the number of constraints $\langle \mathbf{x}, \mathbf{v}_j\rangle \geq 0$ which are satsificed, and $\mathbf{x}$ satifies all constraints.

However, the problem becomes much more interesting if we dont allow degenerate solutions. In fact, by removing $\mathbf{x} = 0$, the problem goes from having a closed form solution, to being NP-hard. It takes a bit of work, but you can actually reduce any integer feasibility program down to your problem.


Let G be k-reguler bipartite graph of degree at least 2. show that K(G) not equal 1?

The statement is false. Here is a counterexample. Let $E$ be the even numbers and $O$ be the odd numbers, and Let $N=\{(n,n+1)|n\in\mathbb{N}\}$. Then $G=(E\cup O, N)$ is a $2$-regular, bipartite graphs, every vertex of which is a cut-vertex.

I won't do your homework for you until you can show where you get stuck, but I'll give you a hint: the conjecture is true for finite graphs, and the proof hinges on this fact. You say, well the resulting components have some number of vertices, and these vertices of one component are distributed between the partitions, so I can count the number of edge ends on either side of the partitions and then you double check if it comes out to the same. It also hinges on the fact that the two partitions are equally big: for a $k$-regular graph $G=(U\cup V, E)$, $|U|=|V|$, a fact which you will have to prove first. The proof for that hinges on the fact that the graph is regular.


Finding Feature Representation Such That Two Samples Are Similar in Feature Space

I think you're looking for metric learning or Manifold learning. At a very high level, the idea behind both of these approaches is to learn the space (or transform) over which a set of (labeled) examples are close to one another.


Is every Turing complete set for EXPSPACE autoreducible?

The result from Buhrman et al. is about EXP rather than EXPSPACE.

Note that Theorem 3.1 from Fortnow's survey is taken from the very same paper of Buhrman et al.


The path between any two nodes in cyclic directed graph

If the graph happens to be a DAG, then you can found the number of paths from any vertex to any other vertex using linear algebra. Let $A$ be the adjacency matrix of the graph. Compute
$$ B = \sum_{k=0}^{n-1} A^k. $$
Then $B_{ij}$ is the number of paths (of length at most $n-1$) between vertex $i$ and vertex $j$. This also works for weighted graphs, in which case the weight of each path is the product of the weights on the edges.

It is easy to construct examples where there are exponentially many paths. For example, let the vertices be $x_0,\ldots,x_n,y_1,\ldots,y_n,z_1,\ldots,z_n$, and the edges be $(x_i,y_{i+1}),(x_i,z_{i+1}),(y_i,x_i),(z_i,x_i)$. The number of paths from $x_0$ to $x_n$ is $2^n$.

If the graph is not a DAG, then there can be infinitely many paths from a vertex to another, since any given cycle can be taken an unbounded number of times. In this case it makes sense to ask for the number of simple paths from one vertex to another. In the weighted version (with weights of polynomial length), we expect this to be difficult, since HAM-PATH can be solved this way.


More efficient vertex-labelling algorithm than BFS?

For graphs that fit into main memory (or even in a largish L3 cache), you probably can't do much better than your library's traversal algorithm without significant effort.

But anyway, you're way into "try and measure" territory. Robert Sedgewick has a nice talk Putting the Science back into Computer Science, that explores flow problems as an example. He uses Ford-Fulkerson, not push-relabel.


How does the processor find kernel code after an interrupt?

On startup, the kernel will initialize an interrupt vector table (called an interrupt descriptor table or IDT on x86) that points to an interrupt handler for each line.

Before the 80286, the IDT was always stored at a fixed address; starting with the 80286, the IDT is loaded using the LIDT instruction.

Interrupt vector tables point to a single handler per interrupt line; that being said, a kernel could choose to, for example, provide an interrupt handler that runs several other interrupt routines, or provide a single handler that covers some or all interrupts. Linux does  these things by providing a generic interrupt handler that determines which interrupt line was called and finds the appropriate downstream handler to call.


This appears to be nothing more than a description of the standard binary notation. List the bits in the string and below them, starting with 1 at the rightmost position and multiplying by 2 at each position to the left:
$$\begin{array}{lccccc}
\mathbf{bits:} & 1 & 1 & 0 & 1 & 0\\
\mathbf{powers\ of\ 2:} & 16 & 8 & 4 & 2 & 1\\
\mathbf{product:} & 16 & 8 & 0 & 2 & 0
\end{array}$$
then add the resulting products: $16 + 8 + 0 + 2 + 0=26$, as it should be, since $\mathtt{11010}_2=26$.

The successive integral powers of 2 are just those that appear in the second line, right to left, and similarly successive bits are those in the first line, again reading from right to left. I must confess to being confused by the phrase except perhaps for the bit in highest position.


How to find all maximal sets $S_i$ of a given array $T$ such that every element of $S_i$ is greater than or equal to the cardinality of $S_i$

Assuming that by maximal sets you mean sets of maximal size (rather than sets which are inclusion-maximal), then there is a very simple algorithm. First, find the maximal size $s$. Second, filter out all elements smaller than $s$. Third, output all subsets of size $s$ of the remaining elements.


Are chatbots a good example of overfitting?

There is no expectation that an Machine Learning (ML) system will perform perfectly. Not just in the practical sense that we obviously haven't yet figured out how to make a human-level chatbot, but in a more formal sense that ML systems, particularly neural nets, but this is true for many other ML algorithms, approximate functions and this approximation is going to have some error.

So the fact that an ML system sometimes produces "incorrect" responses doesn't indicate anything. Overfitting is when the ML system performs extremely well on the training set and catastrophically poorly for even relatively small departures from the training set. To show this requires showing poor performance on many examples which are near the training set. Overfitting is unlikely when the training set is large compared to the number of parameters of the ML system (e.g. the weights of a neural network).

You can get nonsensical answers just as well from underfitting or false generalizations. The ML system can easily "learn" a "rule" that makes sense in some situations but not all but be either unable to model (underfitting) or unaware of (false generalization) the exceptions.

At the extremes, you're just off distribution, meaning the input you're giving the system is very unlike the input it was trained on. Obviously at this point there's no reason to expect it to perform well in any sense. An extreme example is training a chatbot on an English language corpus and then talking to it in Spanish.


That's not a misprint.  $kA \bmod 1$ makes sense.  For instance, $37.239 \bmod 1 = 0.239$.


Comparison-based lower-bound for finding duplicates in an array of $n$ numbers

Your problem is known as element distinctness. You can find $\Omega(n \log n)$ lower bounds for several computation models in the answers to a question on cstheory. The lower bound for the comparison model is particularly simple.


You prove that vertex cover reduces to some problem A, does that mean that A is NP-Complete?

Let's start with the relevant definitions:

  A problem $A$ is NP-complete if:

  $A$ is in NP, and
  $A$ is NP-hard.

  A problem $A$ is NP-hard if for every problem $B$ in NP, there is a polytime reduction from $B$ to $A$.

Using these definitions, you can prove the following result:

  If a problem $B$ is NP-hard and there is a reduction from $B$ to $A$, then problem $A$ is also NP-hard.

Applying this to your problem, if there is a reduction from vertex cover to $A$, then $A$ is NP-hard. If $A$ is also in NP, then it is furthermore NP-complete. Whether P=NP or not has absolutely no bearing on this.

Note that there are NP-hard problems which are provably not in NP. For example, the halting problem is NP-hard, but is known not to be in NP.


I think in this scenario you can just bubble-up one of the updated element to restore the max-heap property.

Notice that by the multiplication you have increased the keys in $V$ children. So the trees rooted at the children still have the max-heap property, but maybe $V$ does not anymore. You can repair this, by swapping the largest key of the children with the key of $V$. This restores the max-heap property for the subtree rooted at $V$. You continue by comparing the key of $V$ with the key of the father of $V$ and swap the key is necessary. You do this, until nothing was swapped, or you reach the root - its the typical heapify routine.

Since binomial heaps have depth at most $\log n$ and the degree is also bounded by $\log n$ the whole procedure needs $O(\log n)$.


Time complexity of removing duplicates in lists

The running time is expected $O(n)$ for both problems.  Simply scan over the input list, and as you examine each item, add it to the hashtable; if it wasn't already present, output it.  The running time is $(n)$ because, with a suitable hash function, the expected time it takes to insert or look up an item in a hash table is $O(1)$.

The worst-case running time with this approach is $O(n^2)$, but you can make the probability of this happening exponentially small with a suitably chosen hash function.

Alternatively, if you care a lot about worst-case running time, you can replace the hashtable with a self-balancing binary tree and achieve $O(n \log n)$ worst-case running time for both problems.


A path modification problem in directed graphs

I am assuming you are using some lists of node pointers at the source nodes for keeping record of outgoing edges and paths.i.e. if you have a source node A which has directed edges towards the nodes B,C and D then you have a list containing pointers to B,C and D which is called $edges$  stored in node A

edges=[B,C,D];

and if some other edges lets say E ,F and G have a directed path towards them then you have a list of paths called $paths$

paths=[E,F,G];

Now let's say you want to delete the paths towards E and F from A then you should remove E and F from paths but still keep it in another list called $forbiddenPaths$.

forbiddenPaths=[];// this list will initially be empty

Here's how the lists will be updated after you have removed E and F from $paths$

edges=[B,C,D];
paths=[G];
forbiddenPaths=[E,F];

This way all you need to do before transmitting data is check if the destination node exists in the $paths$ list.If it does then transmit otherwise don't.You can also keep a $forbiddenEdges$ list in the same manner for avoiding some edges of your choice.


In the RAM model, variables hold a machine word, and operations on machine words take $O(1)$ time. The question is how big should a machine word be. In the variant of the RAM model used in CLRS, a machine word should be large enough so that a variable can count from 1 to $n$ (this is the meaning of the phrase "enabling us to index the individual elements"). To count from 1 to $n$ you need roughly $\log_2 n$ bits, or more accurately, $\log_2 n + O(1)$ bits. This is why we need $c \geq 1$; note that $c$ need not be an integer.

In the RAM model, indexing an array requires that the index is held in a single variable (or at least, this is one reasonable definition). This is why it is important that the machine word is large enough to index all arrays that could appear in an algorithm. If we only consider polynomial time algorithms, then all arrays have polynomial size, and so require indices of size $\Theta(\log n)$. This is the bare minimum needed to make the RAM model useful. It turns out that a larger machine word is not usually necessary, and so $\Theta(\log n)$ is a good choice.

Another reason that we want machine words to be able to hold indices (even if we somehow modify the indexing operation to handle an index spread across several machine words) is that we want a loop of the form

for i from 1 to n:
     if i equals j then do something that takes O(1) time

to run in time $O(n)$. This implies that the operation of incrementing an index should be $O(1)$, and that the operation of comparing two indices should be $O(1)$. So we want our machine words to be large enough to contain an entire index.


Finding a path crossing minimum number of distinct colors

For a constant number of colors, the problem can be solved by considering all possible subsets of colors. The rest can be solved using a shortest path with memoization.

You can reduce set cover to this problem: Build a grid with $m+2$ rows and $n+2$ columns. Also assume all points in one column are connected, but connect the points in rows based on the following rule:

Each column represents a member of the universal set and each row a set. The boundary is a color with weight zero. Let $s$ be the leftmost uppermost point and $t$ be the rightmost and lowest point and remove the other two corners of the grid. Color the point $i,j$ with color $i$ if set $S_i$ contains $u_j$ and remove it otherwise. The minimum weight path in this graph is the same as the minimum set cover.

This subset of a grid, is a unit disk graph: allow the columns to be $cn$ apart from each other, where $c$ is the vertical distance between the first row and last row.
So $\theta(\log n)$ is tight.


Finding a subset in bipartite graph violating Hall's condition

Let $G=(X,Y,E)$ be a bipartite graph with $|X|=|Y|=n$ having a maximum matching $M$. Consider the directed graph $G'$ on the vertex set $X \cup Y$ which includes the edges of $G$ oriented from $X$ to $Y$ and the edges of $M$ oriented from $Y$ to $X$. Let $U \subseteq X$ be the set of vertices of $X$ unmatched in $M$, and let $S$ be the set of vertices reachable from $U$ in $G'$. Then $|N(S \cap X)| = |S \cap X| - (n-|M|)$.

For the proof, let us first notice that $|N(S \cap X)| \geq |S \cap X| - (n-|M|)$, since otherwise each matching would have to miss more than $n-|M|$ vertices of $S \cap X$. It remains to show that $|N(S \cap X)| \leq |S \cap X| - (n-|M|)$. The idea is to show that $|X \setminus S| + |S \cap Y| \leq |M|$. Given this, note that by definition $N(S \cap X) = S \cap Y$, and so
$$ |N(S \cap X)| = |S \cap Y| \leq |M| - |X \setminus S| = |M| - (n-|S \cap X|) = |S \cap X| - (n-|M|). $$

To finish the proof, we show that $|X \setminus S| + |S \cap Y| \leq |M|$. We do this by showing that each vertex in both of these sets belongs to $M$. For each $(x,y) \in M$, if $y \in S$ then $x \in S$, showing that at most one vertex is counted in $|X \setminus S| + |S \cap Y|$ for each edge in the matching, proving the inequality. It is clear that each vertex in $X \setminus S$ belongs to $M$, since by definition unmatched vertices belong to $S$. The crux of the proof is showing that each vertex in $S \cap Y$ belongs to $M$. Indeed, if some $y \in S \cap Y$ didn't belong to $M$, then the path proving that $y \in S$ is an augmenting path for the matching: if we remove all edges going from $Y$ to $X$ on the path and replace them by all edges going from $X$ to $Y$ on the path then we obtain a matching with one more edge than before. Since we assumed that $M$ is a maximum matching, this is impossible, completing the proof.


Best Algorithm for searching for an index in an array such that A[i] = i

Notice that the index of the element of the array requires $\Omega(\log(n))$ bits to represent. This means that there can be no better algorithm than $O(\log(n))$ to find this index.

Edit:
To elaborate a bit, what you have is a binary search algorithm which works in $O(\log(n))$. What you want to prove is that any other algorithm for the same problem will work in no less than $O(\log(n))$.
The proof involves information theorethic reasoning, since storing $n$ different numbers (the indices of the array) requires each to be represented by no less than $\log(n)$ bits.
Now we can see, that in order for you to output/write the solution you need $\Omega(\log(n))$ bits, and you cannot do away with less (we can apply the same reasoning to comparisons since we need to compare $\log(n)$ bits to deduce whether one number is less than the other if they are the same on all but the last bit)
This means that any algorithm will need atleast $O(\log(n))$ operations to produce output.

Now, obviously, since you have produced an algorithm working in $O(\log(n))$ then the bound is sharp.

to answer your question in the comment to this answer:

this information of log n bits on index is valid on unsorted array as well? why do we not have an algorithm to search an unsorted array in log n time? kindly elaborate whether or not is this valid for both ordered and un-ordered arrays?

while this is true for both unsorted and sorted arrays, it merely specifies a lower bound on the complexity of algorithms.
This means that no algorithm can do better than $O(\log(n))$. It does not guarantee that there exists one though.

In an unordered array there are extra complexities that arrise, which prevent an $O(\log(n))$ solution. So we might say that the $\Omega(\log(n))$ is not sharp in this case since there does not exist an $O(\log(n))$ algorithm which could solve this problem for an unsorted array.

If we were to find a sharp lower bound for the unsorted array problem then we would need to use different assumptions and conduct a different analysis.

An important thing to realise is that this is all dependent on the underlying model of computations used. Is it assumed that comparisons take $O(1)$? How about writing a number to memory? If this is not defined then estimating complexity is tricky to say the least.


Time complexity of optimal algorithm for solving this problem

$O(n^2 log n)$ is easy: Create a sorted array of the items in the first row. Lookup the items in the second row in this array using binary search, and remove items that were not present. Same with the third row etc. The last remaining item is the largest one present in evert row. The main effort is $n^2$ lookups in an array of size n.

Using a hash table probably makes it $O (n^2)$.


So here is a pseudo code of what i proposed. Maybe i was not clear.

1) Start with a node (Your start node)

2) For each node from root node, try to find a node (if it exists) that has atleast one node that is not visited. (If the graph is a cyclic, this condition is true). To do this, you may use a hashset of visited children for each iteration.

3) do the above till you reach a node which has no children. Thats the end of the algo where you found 1 tree in the graph. For back tracking i think you want to maintain a hashmap of all the nodes that you started with and the value field contains all the connected nodes to the graph. The point you reach a leaf node without violating point(2), you start back tracking to find the parent of the current node; ie the leaf node to the start node.

Thats your subgraph which is a tree.

PS- Leaf node in this case would be a node which has no nodes connected to it/all the other nodes connected to it are already visited previously/only inward connections


Integer factorization: comparing with floor

The value of $c$ is given by the formula
$$ c = \frac{(a/x) \pmod{e}}{e}. $$


Finding growth of "inter-recursive" functions

Growth and time complexity are not the same, though in this case they probably have similar values (up to a multiplicative constant). The recurrences for the time complexity are
$$
\begin{align*}
F(x) &= \begin{cases} \Theta(1) & x < 1, \\ F(x-1) + G(x) + \Theta(1) & x \geq 1. \end{cases} \\
G(x) &= \begin{cases} \Theta(1) & x < 2, \\ F(x) + G(\lfloor x/2 \rfloor) + \Theta(1) & x \geq 2. \end{cases}
\end{align*}
$$
If you're uncomfortable with the notation $\Theta(1)$, mentally replace it with $1$. The difference between these recurrences and the ones for $f,g$ is the addition $\Theta(1)$ term in the inductive case (second lines above).

Ignoring the floors for the moment, we have
$$ g(x) = f(x-1) + f(x/2-1) + f(x/4-1) + \cdots, $$
the sum ending when the argument is below $1$. Therefore
$$ f(x) = f(x-1) + g(x) = 2f(x-1) + f(x/2-1) + f(x/4-1) + \cdots. $$
The recurrence $f'(x) = 2f'(x-1)$ with a base case $f'(0) = 1$ already has the solution $f'(x) = 2^x$, so we know that $f(x) = \Omega(2^x)$. Since $2^x$ grows so fast, we know that $f(x/2-1) + f(x/4-1) + \cdots \ll 2f(x-1)$, and this shows for example that $f(x) = O((2+\epsilon)^x)$ for all $\epsilon > 0$.

At this point one can probably guess and prove an asymptotic formula for $f$, but I'll leave that for others to do. Given $f$, it should be easy to estimate $g$. Indeed, it seems probable that $g = \Theta(f)$.

Update: Experiments show that
$$
\begin{align*}
\frac{f(n)}{2^n} &\longrightarrow 1.9635473337171197318620139352\ldots\\
\frac{g(n)}{2^n} &\longrightarrow 0.98177366685855986593100696758\ldots
\end{align*}
$$
Let $\alpha = \lim_{n \to \infty} f(n)/2^n$.
Even more accurately, we get (for $n$ divisible by $4$)
$$
\begin{align*}
f(n) &= \alpha \left( 2^n - 2^{n/2} + \frac{11}{28} 2^{n/4} + O(2^{n/8}) \right), \\
g(n) &= \alpha \left( \frac{1}{2} 2^n - \frac{1}{4} 2^{n/2} + \frac{1}{14} 2^{n/4} + O(2^{n/8}) \right).
\end{align*}
$$
The curious reader can try to prove these expansions, up to the exact value of the constant $\alpha$.

Indeed, let $f'(x) = f(x)/2^x$. Then
$$ f'(x) = f'(x-1) + 2^{\lfloor x/2 \rfloor - 1 - x} f'(\lfloor x/2 \rfloor - 1) + \cdots. $$
Easy induction shows that $f'(x) = O(x)$ and so
$$ f'(x) = f'(x-1) + O\left(\frac{x\log x}{2^{x/2}}\right). $$
Since the series $\sum_{x \geq 1} (x\log x)/2^{x/2}$ converges and the sequence $f'(x)$ is increasing, $f'(x)$ tends to some limit. Using the estimate $f'(x) = \Theta(1)$ and being more careful, we obtain
$$ f'(x) = f'(x-1) + \Theta(2^{-x/2} + 2^{-3x/4} + \cdots) = f'(x-1) + \Theta(2^{-x/2}). $$
Let $C = \lim_{t \to \infty} f'(t)$. Then
$$ f'(x) =  C - \Theta\left(\sum_{t=x+1}^\infty 2^{-t/2}\right) = C - \Theta(2^{-x/2}). $$
This shows that
$$ f(x) \sim C 2^x - \Theta(2^{x/2}), $$
which in turn implies that
$$ g(x) = f(x) - f(x-1) = \frac{C}{2} 2^x \pm O(2^{x/2}). $$
The rest of the terms in the asymptotic expansion depend on the LSBs of $x$, and are left to the interested reader.


The result will be an empty table.

The steps are :

delete (4,3)
delete rows with B = 4        --> (2,4), (5,4)
delete rows with B = 2, B = 5 --> (9,2)
delete rows with B = 9        --> (3,9)
delete rows with B = 3        --> (1,3)


What is space complexity of shrinking one array to increase another?

Space complexity is all very well on something like a Turing machine: you just define the space complexity to be the number of different tape cells that the tape head visits.  For real computers, things get much more complicated and very implementation-dependent.

It is possible that the algorithm you describe runs in constant space. If the array a is stored earlier in memory than the string b, the system could, in principle, delete the last character of a, shuffle everything after it back one memory cell, then add a character onto the end of b, so no extra memory is used.

In reality, though, it's much more likely that the system doesn't keep moving things around and just allocates new memory each time a character is added to b, which is probably linear space. Except it could be worse. Maybe, every time you try to make b bigger, the system actually allocates completely new storage for the extended string, which could give quadratic space usage.  Or maybe it's not that dumb and, each time you extend the string beyond its current memory allocation, it allocates a new chunk of memory that's double the size, so it can do lots of appends without reallocating memory every time. That would be linear, again.

And in real reality, what actually happens probably depends very much on what else is running on the machine. If there's lots of free memory, the system might be very happy to allocate fresh memory each time you extend the string, and it might only free the memory used by the old versions right at the end. If there is little free memory, it might free up unused memory much more aggressively.

So your code probably uses at least a linear amount of memory, but it's not really possible to be more precise than that.


Expected number of vertices with degree 2

Hint:

   Indicator random variables.

If that's not enough and you need a second hint:

   Use linearity of expectation.


Represent unsigned 12-bit octal numbers. Results in octal


There is no way to ensure that exactly 4 people win, and that all people have an equal likelihood of being chose.

For instance, suppose you see 100 people during from 8am-3pm, and have given out 3 awards.  Then, if 500 people all show up in the last hour, you have at most one more award to give out, so those people will have a much lower chance of winning.  Alternatively, suppose you see 100 people from 8am-3pm and have given out 0 awards.  Then, if 4 people show up the last hour, the only way to give out exactly 4 awards is to give each of them an award, so those people will have a much higher chance of winning.

As a result, there probably is no perfect solution -- you will just be trading off different kinds of imperfection.

One solution is to not give anyone an award, but that's not very useful.

A practical solution is probably to get some data beforehand on the estimated number of people who show up per day, and use that to choose the probability of winning for each person.  Once you've given out 4 awards, stop.  For instance, suppose on average 100 people show up per day.  Then as each person arrives, with probability $0.04$, given them an award.  If you hand out 4 awards, no one else gets one for the rest of that day.  That ensures that the expected number of awards handed out is a bit less than 4; that you won't hand out more than 4 awards; and that everyone's probability of winning is close to the same.

If you don't need to determine in real time whether each person has won, you can use reservoir sampling.


why it said the "The left recursion has been removed at the cost of an extra non-terminal symbol(E1) and a little extra complexity"?

That grammar has recursion but not left recursion.  Check the definition of left recursion (e.g., https://en.wikipedia.org/wiki/Left_recursion, or consult your favorite textbook on formal languages).


What is this data structure/concept where a plot of points defines a partition to a space

What you described is Voronoi diagram.
Here is an excerpt from Wikipedia.

In the simplest case, shown in the first picture, we are given a finite set of points ${p_1, \cdots, p_n}$ in the Euclidean plane. In this case each site $p_k$ is simply a point, and its corresponding Voronoi cell $R_k$ consists of every point in the Euclidean plane whose distance to $p_k$ is less than or equal to its distance to any other points. Each such cell is obtained from the intersection of half-spaces, and hence it is a convex polygon. The line segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.


Select the n closest nodes from a starting node in a weighted directed graph

Question 1. For very large graphs, the canonical Dijkstra algorithm will not work because you must enqueue every node first.

Yes, you are right about the disadvantage of canonical Dijkstra's algorithm. However, it can be easily adapted (wiki):

  The algorithm can start with a priority queue that contains only one item, and insert new items as they are discovered (instead of doing a decrease-key, check whether the key is in the queue; if it is, decrease its key, otherwise insert it).

See the paper for details (including experiments) on implementing Dijkstra's algorithm with such a modified priority queue.

  Question 2. I'm interested in things like how do you know when you've found all the shortest paths for the closest nodes, without traversing the entire graph in the process.

The Dijkstra's algorithm finds the shorted paths from a starting node in the order of increasing costs. So, the first $n$ vertices removed (delete-min) from the priority queue are the $n$ closest nodes from a starting node you are looking for.


Yes, you can.  As Dmitry explains, CYK parsing can be used to parse a linear grammar in $O(n^2)$ time, where $n$ is the length of the input word.
CYK parsing is a dynamic programming algorithm that  sets $P[l,s,R]$ to be true if $a_{s .. s+l-1}$ can be generated from the non-terminal $R$, where $a_{1..n}$ is the input word.
Note that there is a recurrence relation that can be used to compute $P[l,s,R]$ from values of the form $P[l',s',R']$ with $l'<l$, in $O(1)$ time.  In particular, if we have the rule $R \to b_1\cdots b_k Q c_1 \cdots c_m$, then we should set $P[l,s,R]$ to true if $a_{s .. s+k} = b_{1 .. k}$ and $P[l-k-m,s+k,Q]$ is true and $a_{s+l-m .. s+l-1} = c_{1 .. m}$.  Do this for each rule with $R$ on the left-hand side.  If none of them sets $P[l,s,R]$ to true, set $P[l,s,R]$ to false.  This takes $O(1)$ time (treating the size of the grammar as a constant).
We repeat this for each of the entries $P[l,s,R]$.  There are $O(n^2)$ such entries (treating the size of the grammar as a constant), and each entry takes $O(1)$ time to compute, so the entire algorithm runs in $O(n^2)$ time.


Why can humans solve certain "undecidable" problems?

Humans can solve some instances of that problem efficiently, but there is no reason to believe that humans can solve all instances efficiently.  Showing one instance that a human can solve efficiently does not imply that humans can solve all instances efficiently.

Undecidable means "there is no algorithm that can solve all instances and that always terminates".  There could still be an algorithm that can solve some instances, even for an undecidable problem.

So there is no contradiction.


Is a Turing Machine a Well-formed formula?

Yes and no. Turing machines aren't WFF, but can be encoded as a WFF. The definition of TMs uses sets and functions (which aren't symbols in the alphabet), but its possible to create a one-to-one encoding from TMs to WFF. Usually, given a TM $M$, we refer to its encoding as $\langle M\rangle$.


Is Myhill-Nerode equivalence class of a language which contains all palindrome pairwise distinct?

Your proof goes also through with a larger alphabet. Let $x,y\in \Sigma^*$, with $x\neq y$. We use as $z$ the word $10^{|x|+|y|+2}1x^{rev}$. Clearly, $xz$ is a palindrome and therefore the word is in the language. The word $yz$ however is not a palindrome. Note that the middle of $yz$ there has to be a $0$ coming from $z$, hence for being a palindrome the middle of $yz$ has to be centered between the two $1$s of $z$. As a consequence, $yz$ is a palindrome only if $x=y$. Thus $yz$ is not in the language.

For the proof you only need that $|\Sigma|\ge 2$. I would say having more letters makes it even easier, since you have more possibilities to choose the split word $z$.


Computational power of nondeterministic type-1 min-heap automata with multiple heaps

Let $\mathrm{SDL}_k$ the shuffled Dyck language with $k$ types of parentheses, i.e.

$\qquad \displaystyle \mathrm{SDL}_k = \mathrm{DL}([_1,]_1) \, ш\, \dots \, ш\, \mathrm{DL}([_k,]_k)$

with $ш$ the shuffle of languages and $\mathrm{DL}(\_,\_)$ the Dyck language with matching parenthesis as specified. Intuitively, any word in $\mathrm{SDL}_k$ contains of $k$ properly nested words of parentheses interleaved arbitrarily; for instance, $[_3 [_1 [_1 [_3 [_2 ]_1 ]_3 ]_2 [_1 ]_1 [_2 ]_1 ]_3 ]_2\in \mathrm{SDL}_3$.

Fact 0: $\mathrm{HAL}_1^{(k)} \subseteq \mathrm{HAL}_1^{(k+1)}$ for $k\geq 1$

Claim 1: $\mathrm{SDL}_k \in \mathrm{HAL}_1^{(k)}$ for $k\geq 1$

Claim 2: $\mathrm{SDL}_{k+1} \notin \mathrm{HAL}_1^{(k)}$ for $k\geq 1$ (the claim is wrong; see below)

Together, fact and claims show that $\mathrm{HAL}_1^{(k)} \subset \mathrm{HAL}_1^{(k+1)}$ and $\mathrm{HAL}_1^{(k)} \subset \mathrm{RE}$ for for $k\geq 1$.

Ad Claim 1: It is clear that $\mathrm{DL}([,]) \in \mathrm{HAL}_1$; min-heaps can implement a counter that is increased by one on $[$ and decreased by one on $]$. A word is accepted if and only if the counter never becomes negative and is zero at the end.

The same principle is used for $\mathrm{SDL}_k$ on a $k$-heap automaton; we maintain one counter per parenthesis type on a dedicated heap each and accept if and only if no counter becomes negative and all counters are zero at the end.

Ad Claim 2: This is more a sketch. In order to accept $\mathrm{SDL}_{k+1}$ an automaton has to be able to check at any time wether $]_i$ is allowed next for any $i=1,\dots,k+1$. As nesting depth and "shuffle depth" are unbounded, finite control can not do this (not even for one parenthesis type). Since a $k$-heap automaton can only access $k$ bits of (heap) information at any time, it has no way of doing the necessary checks.

Claim 2 is in fact false. We have to be remember that type-1 heap automata can essentially store a finite amount of counters but can only access the top most. With two heaps, we can access all counters of the first heap: if we want to access counter $i$, move the symbols encoding counters $1,\dots,i-1$ to the second heap, access counter $i$ and move everything back. That leads us to the following claims:

Claim I: $\mathrm{HAL}_1 \subset \mathrm{HAL}_1^{(2)}$

Claim II: $\mathrm{HAL}_1^{(2)} = \mathrm{HAL}_1^{(3)} = \dots$

Claim I follows from above reasoning with $\mathrm{SDL}_2$. Claim II holds because $k$-heap automata can only manage finitely many counters, no matter the $k$, which can be simulated by a $2$-heap automata as outlined above.

This train of thought leads us to

Claim III: $\mathrm{HAL}_1^{(2)} \subset RE$

as Turing machines can handle unbounded numbers of counters, outclassing $2$-heap automata. As a concrete example, consider

$\qquad \displaystyle \mathrm{SDL} = \bigcup\limits_{k\geq 1} \mathrm{SDL}_k.$

Note that $\mathrm{SDL}$ can be expressed using a finite alphabet by encoding $[_i$ as e.g. $[\{\overline{i}\}$ with $\overline{i}$ the binary representation of $i$ and $]_i$ similarly.


How to query and update ranges of arrays?

Break the array up into $O(\sqrt{n})$ contiguous groups, each of size $O(\sqrt{n})$. With each group, store:

A balanced binary search tree (BBST) containing the values of the elements in the array as keys and a pointer to their location in the group as a value.
A modifier, $\delta$, indicating some offset that all of the elements have from $0$. For instance, if the elements are stored as $1,2,3$, but actually have the values $-11,-10,-9$, $\delta$ should be $-12$. The idea of $\delta$ is that decreasing the value of all of the elements in a group takes $O(1)$ time.
The array elements themselves in array order

To decrease the elements in a range $[R,L]$ where $R$ and $L$ are in the same group, just walk the array and update the BBST for each element. This takes $O(\sqrt{n} \lg n)$ time.

Te decrease the elements in an entire group at once, update $\delta$. This takes $O(1)$ time.

Every range contains $O(\sqrt{n})$ groups at most, and at most two of them are not wholly contained in the range - the end groups. Thus, to decrease a range $[R,L]$ takes $O(\sqrt{n} \lg n)$ total time

To count in a group, find the number of elements in the binary tree less than $-\delta$. This takes $O(\lg n)$ time in a BBST where the nodes are annotated by the sizes of their subtree.

To count in a part of a group, iterate over the array values in that part of the group and count how many are less than $-\delta$. This takes $O(\sqrt{n})$ time.

Again, every range contains $O(\sqrt{n})$ groups at most, and at most two of them are not wholly contained in the range - the end groups. Thus, to count a range $[R,L]$ takes $O(\sqrt{n} \lg n)$ total time


prove that minimal number of comparisons to find median among five elements is 5

Your proof is correct. But I don't think 5 comparisons is achievable.
Here is the algorithm that finds the median in 6 comparisons.

Sort the first two pairs. [ 2 comparisons]
Order the pairs w.r.t. their respective larger element. [ 1 comparison]

Call the result $[a,b,c,d,e]$; we know $a<b<d$ and $c<d$.
Now there are 3 elements less than $d$, hence $d$ can't be the median( i.e. $3^{rd}$element of the sorted array)
WLOG say $c<e$ and $a<b$ (known already). Order the pairs w.r.t. their respective larger element. WLOG $a<b<e$ and $c<e$. Compare $c$ & $b$, greater one is the median.
[ 3 comparisons - 1 for $c$ & $e$, 1 for ordering the pairs and  1 for $b$ & $c$ ]

Hence, total number of comparisons is equal to 6.

Idea taken from here .


What is wrong?

So, this is how I solved
$T(n-1) \approx{}  T(n-2)$
$T(n) = T(n-1)^2$

An equality is the most precise and most powerful entity in the world. Please treat it with due respect.
Let me show how wrong it is if you use approximation liberally with equalities. If your argument above is sound, we can also do the following.
$\quad T(n) \approx{}  T(n-1)$
$\quad T(n-1) = T(n-1)*T(n-2)$
$\quad T(n-2) = 1$  if $T(n-1)$ is not 0.
So $T(n)$ must be 0 or 1 from time to time . That is obviously false, however.  For example, we can let $T(1)=T(2)=2$.

What to do?
What you can do is, as gnasher729 suggested, "taking logarithm on both sides immediately", assuming $T(1)>0$ and $T(2)>0$, which can be assume generally when we are analyzing recurrence relations in computer science.
You can also, of course, dive into analysis by cases when $T(1)$ and $T(2)$ might be 0 or even negative.


Trace dependents & precedents of a program in an imperative language

The analysis you want is called reaching definitions in the compiler community.

For your case you would put a "fake" definition of each variable you are interested in at the beginning of the program (representing definitions that are entering your script from outside) and then determine whether that definition reaches any of the uses.  If no fake definition reaches any use then the variable is defined inside the script, otherwise its value may be coming in from outside. The interesting cases involve conditionals and loops (some variables may be defined on one side of a conditional and not the other.)

I can highly recommend the following text books if you want to learn more:

Aho, Alfred V.; Sethi, Ravi;  Ullman, Jeffrey D.: Compilers: Principles, Techniques, and Tools, 1986.
Cooper, Keith D.; Torczon, Linda: Engineering a Compiler, 2005.

Reaching definitions analyzes scalars (so you would analyze each a[i,j] independently, as you did in your example.)

You could try to analyze entire arrays simultaneously, but this is a research topic (because parts of the array can be defined and other parts not).  The classic papers on trying to analyze entire arrays are

Zhiyuan Li: Array privatization for parallel execution of loops. Int'l Conf on Supercomputing, 1992.
Dror E. Maydan, Saman P. Amarasinghe, and Monica S. Lam: Array data-ﬂow analysis and its use in array privatization. Symp Principles of Programming Languages, (POPL-20):2-15, 1993.
Peng Tu and David Padua. Automatic array privatization. Int'l Workshop
on Languages and Compilers for Parallel Computing, (LCPC-6):500–521, 1993.


Solving $T(n)=4T(n/4)+\log n$ using master theorem

Let's use the other method to solve recurrences, namely, repeated substitution, assuming that $n$ is a power of 4:
$$
\begin{align*}
T(n) &= \log n + 4T(n/4) \\ &=
\log n + 4 \log(n/4) + 16T(n/16) \\ &= \cdots \\ &=
\log n + 4 \log(n/4) + 16 \log(n/16) + \cdots + (n/4) \log (n/(n/4)) + n T(1) \\ &=
(n/4) \log 4 + (n/16) \log 16 + \cdots + (n/n) \log n + nT(1) \\ &=
n \log 4 \left(\frac{1}{4^1} + \frac{2}{4^2} + \cdots + \frac{\log_4 n}{n}\right) + nT(1) \\ &=
\frac{\log 4}{9} (4n - 3\log_4 n - 4) + nT(1) \\ &=
\left(\frac{4\log 4}{9} + T(1)\right)n - \frac{\log n}{3} - \frac{4\log 4}{9}.
\end{align*}
$$
In particular, we see that $T(n) = \Theta(n)$.

Intuitively, what happens is that, roughly speaking, the dominant terms are $(n/4)\log(n/(n/4)) = (n/4)\log 4$ and $nT(1)$, which are both $\Theta(n)$; in the former term the logarithm is applied to a constant, and so the fact that the recurrence has $\log n$ rather than, say, $\log^2 n$ only affects the resulting hidden constant, but not the asymptotic complexity.


What is the difference between assignment, valuation and name binding?

Binding has to do with giving names to things (or values) in a given well delimited context. Assignment is about storing things (or values) in some location (a variable). Another assignment can replace a previous value with a new one. Valuation consist in binding all the identifiers of a formal text with something (with a value).  In mathematics these identifiers are often called variables, which causes a confusion with the concept of variable (i.e. memory storage) in computer science.

Trying to give more intuitive details

Name binding attaches a meaning to identifiers within some part
(called scope) of the concerned mathematical or programming text.
This meaning can indeed be seen as a value in some domain when the
text is interpreted.

For example, if you declare foo as an integer variable, the value
attached to foo within the scope is an integer variable. An integer
variable may be seen informally a a container that can carry an
integer value, which may be changed. You can also see it as the address of a
place in memory where the content may be stored.

But if you declare foo as the integer 25, then whithin the scope,
any use of foo is identical to a use of 25. If you declare foo as an
integer constant, it cannot change and thus its value must be
specified.

Binding is attaching a name to some value that does not change within the scope of the name. An example is a legal documents stating that "for the purpose of this document, Mr. Brown, and the Smith family shall be called the beneficiary." The scope is the legal document. And everywhere in the document, the use of the word beneficiary means Mr. Brown, and the Smith family. You can see it as a definition of a local terminology. It has to do with giving names to things. Binding is about speaking, reading or writing. It is not about executing or moving values around: that corresponds to assignment.

A variable may be seen as a chunk of memory that can contain a value,
When you have a variable, you can change the value contained in this variable
contains with an assignment. If foo is bound to (or denotes) a variable in
the current scope, you can assign a value to foo, i.e. to the
variable denoted by foo, or read the value contained in that
variable. And you can change that value with a new assignment.

So binding is an operation that tells what is the meaning of names in
the text of the program or of the mathematical discourse. It is
static, in the sense that the text does not change. But
assignment is a programming concept that consist is storing a value in
a variable, i.e. a container, which is usually a place in memory. It
is a dynamic concept related to how (representations of) values are
stored in memory, which changes as the program progresses.

Note that a variable may exist independently of any name to which it could be bound. This is the case for an element of an array, to take a simple example.

In various contexts, one may consider expressions or texts that use
names that have not been defined. For example you can write
$(a^2-b^2)/(a-b)$ which is an arithmetic expression. Then you may
valuate the variables by associating an environment (you may read
approximately a scope) where the variables $a$ and $b$ are bound to some
values, for example 3 and 12, and be interested in the value taken by
the exression.  A valuation is such an association of a set of names,
each with a specific value. The name valuation is used more in formal mathematics, while assigment is a programming concept.


Floating Point Systems - Rounding Error in Taylor series

Yes, that's exactly why: it's due to floating-point roundoff error, due to the alternating signs.

Suppose you have $x=10^{100}$ and $y=10^{100}-1$, and you ask your computer to subtract $x-y$.  We know what the correct answer should be: it should be $1$.  However, when $x$ and $y$ are represented as floating-point numbers, you don't get $1$ as the answer.  Floating-point representation is not exact for large numbers, so $10^{100}$ will get rounded off to the nearest number that can be represented in the floating-point representation.  As a result, $x$ won't be exactly $10^{100}$; it'll be a bit larger or a bit smaller -- and while the relative error will be very small ($< 0.1\%$), the absolute error might be very large ($x$ might be $10^{100}+\delta$ where $\delta$ is in the billions or much larger).  The same is true for $y$.  Thus, when you subtract $x-y$, the result won't be exactly $1$; it could be off by an absolute error of billions or much more.  As a result, computing $x-y$ in floating-point arithmetic will give you answer that is wildly wrong.

In contrast, if you compute $x+y$ where $x=10^{100}$ and $y=10^{100}-1$, the answer will be reasonable.  It won't be exactly correct, but it will be very close to correct.

To put it another way: suppose you compute $x+y$ and $x-y$ where $x \approx y$ and $x,y$ are very large.  Then $x+y$ will be reasonably accurate, but $x-y$ will be wildly inaccurate.  In particular, suppose that the closest representable floating-point number to $x$ is $\tilde{x}$, and the closest representable floating-point number to $y$ is $\tilde{y}$.  We know that floating-point arithmetic has small relative error, so $\tilde{x} = x \times (1+\epsilon_x)$ where $\epsilon_x$ is small (say, $|\epsilon_x| \le 2^{-20}$), and $\tilde{y} = y \times (1+\epsilon_y)$ where $\epsilon_y$ is small.  Now

$$\tilde{x} - \tilde{y} = x - y + x \epsilon_x - y \epsilon_y \approx x-y + x \times (\epsilon_x - \epsilon_y),$$

so the absolute error could be as large as $x \times (\epsilon_x- \epsilon-y)$.  We know that $\epsilon_x - \epsilon_y$ will be no bigger than $2^{-19}$ or so, but if $x \approx 10^{100}$, their product will be enormous: the absolute error could be as large as $10^{100} \times 2^{-19}$, which is enormous.  Since the correct answer is $x-y \approx 0$,  the relative error will also be enormous.

In contrast,

$$\tilde{x} + \tilde{y} = x+y x \epsilon_x + y \epsilon_y \approx x+y + x \times (\epsilon_x + \epsilon_y),$$

and here $x \times (\epsilon_x + \epsilon_y)$ might be as large as $10^{100} \times 2^{-19}$ or so, which is enormous.  So, the absolute error in this case is also large.  However, the relative error is small: $10^{100} \times 2^{-19}$ is quite small compared to the correct answer, $x+y \approx 2 \times 10^{100}$.  In particular, the relative error will be on the order of $2^{-19}$ when computing $x+y$ using floating-point math.

So, that's why absolute signs cause problems but the same sign doesn't cause problems.

For further explanation, you might enjoy reading the following article, especially Section 1.4:

What Every Computer Scientist Should Know About Floating-Point Arithmetic.  David Goldberg.  ACM Computing Surveys, 23:1, March 1991.

Separately, one other thing to know about Taylor series approximations is to have a feeling for the range where they are likely to be accurate.  In practice, we always truncate the Taylor series after a finite number of terms -- the full Taylor series is infinite, so we can't sum the entire series; instead, we sum just the first $n$ terms, for some finite $n$.

If you truncate the Taylor series for some function $f(x)$ after $n$ terms, you get an approximation to $f(x)$.  How good an approximation is this?  There are various bounds on the error of this approximation.  One bound is

$$\text{error} \le {|x-a|^{n+1} \over (n+1)!} \times \max \{f^{(n+1)}(v) : a \le v \le x\},$$

where we're using the first $n$ terms of the Taylor series approximation around $a$, and where we evaluate this at $x$ for some $x\ge a$.  So, if you can upper-bound the value of the $n+1$-th derivative of $f(x)$, you can get a bound on how good an approximation the truncated Taylor series will be.  You can read more about this at https://en.wikipedia.org/wiki/Taylor_series#Approximation_and_convergence and http://norsemathology.org/wiki/index.php?title=Taylor_Series_as_Approximations and https://en.wikipedia.org/wiki/Taylor%27s_theorem#Example.

In general, when you use a Taylor series approximation centered around $a$, you usually want to choose $a$ to be near $x$: the closer it is to $x$, the more accurate the approximation will be.  Also, the more terms in your sum, the more accurate the approximation will be.

Once you have an upper-bound for the quality of the Taylor series approximation, you can now figure out how many terms you need to sum.  Note that this analysis assumes infinite-precision numbers and ignores the issues due to floating-point round-off.  So, to get an accurate answer, you need to ensure two things: (a) pick a Taylor series approximation with enough accuracy that it would give a good answer if you used infinite-precision numbers, and (b) you need to account for round-off error, to ensure that when you do the calculation with floating-point numbers you get a result that is close enough to what you would have gotten with infinite-precision math.


Why scholarly papers focus on DAGs instead of DCGs (Directed Cyclic Graphs)

Let me mention one thing which is absent in the other answers: DAGs actually occur in applications. For example, a Boolean circuit is an ordered DAG whose vertices are labeled by logic gates. Dependencies of various sorts, like prerequisites for different parts of a project, also form a DAG. Wikipedia has many other examples.

Some problems can only be stated for DAGs. For example, topological ordering only makes sense for a DAG. Other problems can be solved faster on a DAG due to its restricted nature. This suggests studying algorithms on DAGs. For similar reasons, there is a lot of literature on algorithms for planar graphs – another naturally occurring class of graphs on which some algorithms run faster.


Machine Learning: What program will derive the underlying algorithm in this series?

Without any a priori knowledge, the problem is insoluble. There are infinitely many possible answers and you have no wat at all to say that one of them is preferable to any of the others. How can you possibly tell just by manipulating symbols that the sequence is "Counting in binary using A and B for 0 and 1" rather than "B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, BABB, BBAA, widgeon, 27, expunge" followed by a list of the squares of every third prime, number written in base-14 using Hebrew letters instead of the even digits?

Wait – how would you even know that there is a next element?


As pointed out by orlp, it's impossible to do in $O(\log n)$ time. However, we can do this in $O(\log N)$ time, where $N$ is the total number of items.
You can do this with 2 Heaps:
The first heap is a max-heap with the smallest $n$ elements. Its root is the $n$-th smallest element.
The second one is the min-heap with the rest of the elements. Its root is the $n+1$-th smallest element.
When max-heap has less than $n$ elements, the operations are trivial. Otherwise:

findNthSmallest() - it's just the root of the max-heap. O(1) time
popNthSmallest():

Pop the root of the max-heap
x := Pop the root of the min-heap
Insert x into the max-heap

push(x):

Push x into the max-heap
y := Pop the root of the max-heap.
Push y into the min-heap.


Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since the integers aren't large enough). Wikipedia lists no known lower bounds, though some people believe that the complexity should be $\Omega(n\log n)$, and there are some bounds in weak models. See for example Lower Bounds for Multiplication via Network Coding by Afshani, Freksen, Kamma, and Larsen.


Proving that language $ L = \{ a^{2n}: n \geq 1\}$ is regular

The pumping lemma states that if a language $L$ is regular then there exists an integer $p$ such that every word $w \in L$ of length at least $p$ has a decomposition $w = xyz$ such that $|xy| \leq p$, $|y| \geq 1$, and $xy^iz \in L$ for all $i \geq 0$.

Your language satisfies the pumping lemma, with $p = 3$ (as it must, since the minimal DFA contains 3 states). Indeed, let $w \in L$ be a word of length at least 3, so that $w = a^{2n}$ for some $n \geq 2$. Then $w$ can be decomposed as follows: $w = xyz$, where $x = \epsilon$, $y = a^2$, $z = a^{2n-2}$. Note that $|xy| = 2 \leq p$, $|y| = 2 \geq 1$, and for all $i \geq 0$, $xy^iz = a^{2n-2+2i} = a^{2(n-1+i)} \in L$ since $n \geq 2$.

The pumping lemma states that every long enough word $w \in L$ has some decomposition $w = xyz$ satisfying the requirements in the lemma. It doesn't claim that all decompositions satisfy the requirements.


Default scan order in SCAN and LOOK disk scheduling algorithms

There is no specific order. In SCAN, C-SCAN, LOOK and C-LOOK we have to start moving towards the closest cylinders as in SSTF or you can start moving towards a direction in which there are less number of requests and then move towards the other


Prove that NP is closed under karp reduction?

I was able to figure it out. In case anyone (mans in ECE 406) was wondering:

$B \in NP$ means that there exists a non-deterministic polynomial time algorithm for $B$. Let's call that $b(i)$, where $i$ is the input to $B$.

$A$ karp reducing to $B \implies$ that there exists a function $m$ such that $m$ can take an input $i$ to $A$ and map it to some input $m(i)$ for $B$, and if an instance of $i$ is true for $A$ then $m(i)$ is true for B (and same for false case),

Therefore, an algorithm for $A$ can be made as follows:

$A (i)$

Take input $i$ and apply $m$ to yield $m(i)$
Apply $b$ with input $m(i)$

This yields an output for $A$. Since both $m$ and $b$ are non-deterministic polynomial time, this algorithm is non-deterministic polynomial time. Therefore $A$ must be in NP.


Intuitive proof for a tree with n nodes, has n-1 edges

You can see a (binary) tree as a directed graph: suppose the root is the "lowest" node and the leaves are the "highest" ones, then say that all the edges are oriented upwards. Then, every node that is not the root will have exactly one edge entering in it, and every edge will be pointing at exactly one node. This means that if you have $n$ nodes, you have to have $n-1$ edges (one per node with the exception of the root).


How to prove that a string is made up of subsequences occurring some arbitrary number of times using concatenation?

Let us first state the theorem that we are trying to prove.

Theorem. Let $w \neq \epsilon$ be a word. Then $w^2 = xwy$ for $x,y \neq \epsilon$ if and only if $w = z^p$ for some $p > 1$.

Proof. Let us first suppose that $w = z^p$ for some $p > 1$. Then $w^2 = z^{2p} = zwz^{p-1}$, where $z,z^{p-1} \neq \epsilon$.

In the other direction, write $w = w_1w_2$, where $|xw_1| = |w_2y| = |w|$. Since $x,y \neq \epsilon$, we see that $|w_1|,|w_2| < |w|$. We have $ww = xw_1w_2y$ implies that $w = xw_1 = w_2y$, and so $x = w_2$ (since $|x| = |w|-|w_1| = |w_2|$). In other words, $w = w_2w_1$.

Now let $w = \sigma_0 \ldots \sigma_{n-1}$, and let $|w_2| = m$. Note that since $|w_1|,|w_2| < n$, we have $0 < m < n$. The equality $w = w_2w_1$ implies (check!) that $\sigma_i = \sigma_{i+m \bmod{n}}$. Let $g$ be the GCD of $m$ and $n$; note that $g < n$. It is known that $g = am + bn$ for some integers $a,b$, and so $\sigma_i = \sigma_{i+bm \bmod{n}} = \sigma_{i+g \bmod{n}}$. Since $g \mid n$, this implies that $w = (\sigma_1 \ldots \sigma_g)^{n/g}$, where $n/g > 1$.


When is cumulative type universes useful?

Without cummulative universes, if you have $A : \mathsf{Type}_3$ then you do not have $A : \mathsf{Type}_7$. Instead, we also have to introduce lifting functions $\iota_{i,j} : \mathsf{Type}_i \to \mathsf{Type}_j$ for all $i \leq j$ and write $\iota_{3,7}(A)$ to port $A$ from the third universe to the seventh one. But this is not all, we also want to know whether $\iota_{3,5}(\iota_{5,7}(A)) = \iota_{3,7}(A)$, i.e., can we lift in several steps? So we need to add a bunch of equations $\iota_{i,j}(\iota_{j,k}(A)) = \iota_{i,k}(A)$ for $i \leq j \leq k$. And this is not all, we also need things like $\iota_{i,i}(A) = A$ and $\iota_{i,j}(\Pi(x : A), B(x)) = \Pi (x : A) \iota_{i,j}(B(x))$, and on and on. It's all very annoying.

With cummulative universes we can just drop all the lifting functions $\iota_{i,j}$.

So why would anyone reject cummulative universes? There are several reasons. An important one is that with cummulative universe it is not true that every expression has at most one type, since a type is an element of many universes. This complicates various algorithms for inferring and checking types. Another reason is semantic: there are interesting models of type theory in which universes are not cummulative.


Is there a way to combine linear equation and inequalities into same equation in order to optimise software calculations?

I find it hard to tell from your question, but your problem sounds like it might be an instance of linear programming, in which case there existing solvers you can use.


i=0, j=size(ar)-1;
while(true)
   increase i to position of first 1;
   decrease j to position of first 0;
   if(i>=j) break;
   ar[i]=0, ar[j]=1;


How to build a graph of people where node connections are determined by name and age?

I assume you want to build the graph of all people, with edges between each pair of people at degree 1.  Once you have this graph, it is straightforward to calculate the distance ("degree") between any two people using standard algorithms.
It's easy to build that graph in adjacency list format; or to store it implicitly and generate the adjacency lists on demand.
Store a hash table that maps from name to a list of all people with that name; and another hash table that maps from age to a list of all people with that age.  Now, given one person, you can use the hash tables to quickly find all other people who have a first-degree relationship with that person, i.e., who are adjacent in the graph.  This lets you build an adjacency list representation of the graph in $O(|V|+|E|)$ time, i.e., linear time rather than quadratic time.
Then, once you have this graph, you can compute distances using BFS in this graph.  Note that you can construct the graph on-the-fly as you execute the BFS algorithm; you don't need to build the entire graph in advance.

Footnote: I'm treating hash table lookups as $O(1)$ time.  This is a reasonable modelling assumption for practical work.  For theoretical work, you can ensure that lookups take $O(1)$ expected time if you use an appropriate hash function, which is nearly as good for most practical purposes.


Mental poker: proving dealt hand is fair

I found out you can prove a hand is fair with the following method:

Every user has a randomly generated "secret" in an input field he can personally edit, before each card is picked all the secrets are sent to the server and hashed seperately, then all the secrets are hashed into a single hash which is used as a seed for the random functions.

Then all the players hashes are sent to every player and being displayed on that players screen, when it is safe, every player is also shown all the other players secret phrases this way:
A) Every player knows that the secrets weren't changed after the game since they have the hashes B) It is impossible for them to find the secrets and get an unfair advantage before it is safe to reveal the secrets C) They can now know that every card is dealt fairly


Why the Call instruction in the x86 architecture saves the return address as EIP+5 instead of 4?

Not sure which book you are referring to (isn't that book talks only about MIPS and not on x86?)

In any case, I think that the answer is the following:
EIP+5 is the address of the next instruction.
That is, in x86 the next instruction after a (near32) call is 5 bytes away. This is because the call takes 5 bytes:
1byte = the call opcode (E8, for a (near)rel32 call)
4bytes = the 32bit offset to the call target from current EIP.

That is, the new EIP (after the call) is computed by taking the current EIP and adding to it the 4bytes relative offset.

So, if the call instruction itself takes 5 bytes, then the next instruction (the return address) is at EIP+5.

See also https://c9x.me/x86/html/file_module_x86_id_26.html for all possible calls (I described the rel32 one).


In context-free grammar (CFG), what is the importance of doing both leftmost and rightmost derivations?

For one particular parse tree there are many possible derivations, depending on the order in which the expansions are done. In a sense, a parse tree represent all of the derivations you'd consider "the same" (as you state). It is easy to see that for a given derivation tree there is exactly one leftmost and one rightmost derivation, which in a sense also represent the set of the derivations you'd deem "the same".

For applications, you are interested in the parse tree as a representation of some underlying structure that has a specific meaning. For example, the parse tree of an expression describes the order in which operations are to be performed. If some string has several parse trees, there is no single meaning (the grammar is ambiguous), that is clearly useless.

Reconstructing a (hopefully the only) parse tree for a string is parsing, different parsing methods reconstruct leftmost or rightmost derivations.


A heuristic for finding a maximum disjoint set

Rather than your approach, I suggest you formulate this as an integer linear program and feeding it to an off-the-shelf ILP solver.  Alternatively, formulate it as a SAT problem and feed it to a SAT solver: you'll probably need to take the decision problem version, where you ask whether there exists a subset of $k$ non-overlapping squares, and then use binary search on $k$.  Those would be the first approaches I would try, personally.

If you definitely want to try your approach based upon a "separating line", then I think the best way to answer your question is going to be to pick a representative set of problem instances, and try some different heuristics on them to see which seems to work best.

My intuition suggests that the best way to select the separator line may be to pick the line $L$ that intersects as few squares as possible, without worrying about how balanced the division is (though if there is a tie among multiple lines that each intersect the same number of squares, you could always use "how balanced the division is" as a tie-breaker).  The reason is that you are getting an exponential multiplicative increase in the running time each time you enumerate all subsets of the squares that intersect the line $L$.  I think your prime consideration is going to be keeping that blowup down.  But that's just my intuition, and my intuition might be wrong.  I think you need to do the experiment to find out empirically what works best.

If you do apply your separating line approach, you might consider using a branch-and-bound approach.  Keep track of the best solution you've found so far (i.e., the largest set of non-overlapping squares you've been able to find so far); say that it is of size $s$ at any point in time.  Now anytime your search tree enters a subtree where you can prove that all solutions below the subtree will have size $\le s$, there is no need to explore that subtree.  For instance, if you have a line $L$ and a subset $X$ where you know that the size of $X$ plus the size of the largest sub collection of non-intersecting squares above $L$ plus the total number of squares below $L$ is $\le s$, then there is no need to recursively compute the largest sub collection of non-intersecting squares below $L$, which saves you one recursive call.  But, if you use an off-the-shelf ILP solver, it will already implement these sort of branch-and-bound heuristics for you -- hence my advice to start by formulating this as an ILP problem and applying an off-the-shelf ILP solver.

Finally, the following paper apparently describes an $O(2^{\sqrt{n}})$ time algorithm to compute the exact solution to your problem.  This is an improvement over the obvious algorithm that enumerates all possible subsets of squares, which takes $O(2^n)$ time.

An application of the planar separator theorem to counting problems.  S.S. Ravi and H.B. Hunt III. Information Processing Letters, Volume 25, Issue 5, 10 July 1987, Pages 317–321.
http://www.sciencedirect.com/science/article/pii/0020019087902067


Stable matching with asymmetric arrays (gale shapley)

This will give you a stable matching when you will use the Gale Shapley algorithm. You can use the below code. a and b are dictionaries in the code

def insert_dummies(a,b):
  length_a=len(a.keys())
  length_b=len(b.keys())
  items_a=list(a.keys())
  items_b=list(b.keys())
  dummy_list=[]
  if length_a>length_b:
    dummy_number=length_a-length_b
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_a:
      f=0
      while dummy_number>f:
        a.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0
    while n<(dummy_number):
      for z in dummy_list:
        b[z]=items_a
        n=n+1
  if length_a<length_b:
    dummy_number=length_b-length_a
    nummer=1
    while nummer<dummy_number+1:
        dummy_list.append("Dummy%d" %nummer)
        nummer=nummer+1
    for i in items_b:
      f=0
      while dummy_number>f:
        b.setdefault(i,[]).append(dummy_list[f])
        f=f+1
    n=0
    while n<(dummy_number):
      for z in dummy_list:
        a[z]=items_b
        n=n+1
    else:
        return

  return a,b

#This function returns the result of the algorithm. Parameter 'a' refers to the preferences of the gender
#that we want to find the optimized solution for, while the parameter 'b' refers to the preferences of the other gender.
def StableMatching(a, b):
    #this function returns a stable matching
    dict_a = a.keys()  #This list contains the names of the group for we are optimizing.
    names1 = list(dict_a)
    dict_b = b.keys() #This list contains the names of the other group.
    names2 = list(dict_b)
    i = 0
    engaged = []
    #This dictionary contains the names of the gender for which we attempt to find the optimized solution.
    times = {}
    t = 0
    position_existing = 0
    position_potential = 0
    counter = 0
    #Can have the values 'free' or 'not free'.
    a_p = {}
    while(counter < len(names1)):
        a_p.update({names1[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Can have the values 'free' or 'not free'.
    b_p = {}
    while(counter < len(names2)):
        b_p.update({names2[counter]: 'free'})
        counter = counter + 1

    counter = 0
    #Initialization of times dictionary.
    while(counter < len(names1)):
        times.update({names1[counter]: 0})
        counter = counter + 1

    #The value -1 has the meaning that when all men or women are paired, the loop stops;
    while((i != -1) and (a_p[names1[i]] == 'free') and (times[names1[i]] < len(names2))):
        #The man/woman who is next in the ranking of the proposals.
        w = a[names1[i]][times[names1[i]]]
        if(b_p[w] == 'free'):
            a_p[names1[i]] = 'not free'
            b_p[w] = 'not free'
            t = (names1[i], w)
            engaged.append(t)
            times[names1[i]] = times[names1[i]] + 1
        else:
            q = 0
            while(q < (len(engaged))):
                  if(w in engaged[q]):
                      t1 = engaged[q]
                      l = 0
                      while(l < len(names1)):
                          if(names1[i] == b[w][l]):
                              position_potential = l
                              l = len(names1)
                          l = l + 1
                      l = 0
                      while(l < len(names1)):
                          if(t1[0] == b[w][l]):
                              position_existing = l
                              l = len(names1)
                          l = l + 1
                      if(position_potential < position_existing):
                          t = (names1[i], w)
                          engaged.append(t)
                          del(engaged[q])
                          a_p[names1[i]] = 'not free'
                          a_p[t1[0]] = 'free'
                          q = len(engaged)
                  q = q + 1

            times[names1[i]] = times[names1[i]] + 1
        i = i + 1
        #If the variable i has passed from all the men/women then it starts from the beginning
        #in order to check the ones who remain single.
        if(i == len(names1)):
            i = 0
        if(a_p[names1[i]] == 'not free'):
            k = 0
            z = False
            while((k < len(names1)) and (z == False)):
                if(a_p[names1[k]] == 'free'):
                    i = k
                    z = True
                k = k + 1
            if((k == len(names1)) and (z == False)):
                i = -1
    engaged_dict = dict(engaged)
    return engaged_dict


Why can't hash tables provide O(n) sorting?

The reason you've never heard of hash tables being used like this is that hash tables are either "too much" or "not enough" in this situation.

If the range of elements being sorted is small, then you can use counting sort, or something similar.  But for counting sort, you would almost certainly want to use a simple array rather than a hash table.  If you know the max and min values of the numbers, then the array can be of size max-min+1, and value x would be associated with index x-min.  By using an array, you avoid the extra complications of hash tables.  Those extra complications are buying you nothing in this application, so hash tables are "too much".

Notice that your "no gaps" restriction ensures that the range of numbers is small (no larger than the number of elements in your original input).
However, if gaps can be present then the range of elements is potentially MUCH larger than the number of elements in your original input.  Then your running time is dominated by the size of that range, NOT by the size of your original input.  Hash tables do not help you deal with those gaps efficiently, so in this case hash tables are "not enough".


Highest Response Ratio Next (Scheduling Algorithm)

It's a variation on Shortest Job Next (SJN) and is an attempt to avoid the starvation problems for estimated long running jobs on busy systems with many short running jobs.

When a job has just hit the scheduling queue it's wait time is zero and it's priority is 1.  As the wait time increases it's priority is increased by a factor weighted by it's ESTIMATED* run time.  Consider 2 processes, one with an estimated run time of 5, the other with 10.  Assuming they are placed in the run queue at the same time, both will have an initial priority of 1.

Process A (s=5)  priority = 1 + 0/5 = 1

Process B (S=10) priority = 1 +  0/10 = 1

As the processes wait, their priority increases proportional to their expected run time, let's say both have waited an interval of 10:

Process A (S=5) priority = 1 + 10/5 = 3

Process B (S=10) priority = 1 + 10/10 = 2

As you can see the priorities of each process increase, but at different rates. After the initial scheduling interval, process A is going to be picked to run before process B.  Once a process is picked to run, its wait time is reset to 0.
Let's assume that process A was picked to run after the previous wait period, but process B had to wait another 10 intervals, and process A became computable again.  The new priorities would be:

Process A (S=5) = 1 + 0/5 = 1

Process B (S=10) = 1 + 20/10 = 3

Assuming other processes with higher priority blocked both processes for another interval of 10 the new priorities become:
Process A = 1 + 10/5 = 3
Process B = 1 + 30/10 = 4

And again both wait 10:
Process A = 1 + 20/5 = 5
Process B = 1 + 40/10 = 5

At this point both processes again have equal priority and either COULD be picked, but on a busy system it's not guaranteed.  If they wait again the new priorities would become:

Process A = 1 + 30 / 5 = 7

Process B = 1 + 50/10 = 6

Again process A becomes the higher priority, but B is still increasing it's priority.  A will be picked first and it's wait again reset to 0, but since B is still accumulating wait time it's priority will keep increasing until it becomes the highest priority on the system and all other processes will have to wait for it to run.

Opinion time:
This seems like a better algorithm than straight SJN, but in practice it could still provide unsatisfactory perceived user response on a busy general purpose system.  Users would perceive a "bursty" system which sometimes gave quick answers, but with long pauses.  I prefer preemptive style scheduling for interactive systems.  For non-interactive systems, this may provide better overall throughput since it reduces expensive context switches.

Note that these are all ESTIMATED run times either based on a default initial value or on the average of the previous estimate and the actual last run time.  This leads to a scheduling problem if the estimate is wildly inaccurate or has a series of short run times followed by a very long run.


The answer should be $\Theta(3^{n/4})$. You can go both ways you suggest – find an exact formula, or estimate the sum, using an integral or in more devious ways. There is no loss in generality if you take $c = 1$. If you replace $n$ with $1$ (so we get a lower bound), then we have
$$ 1 + 3 + 3^2 + \cdots + 3^{n/4} = \Theta(3^{n/4}), $$
using the formula for summing a geometric series. If you bring back the $n$, the calculation becomes a bit more difficult, but you should still be able to get a matching upper bound:
$$
n + 3(n-4) + 3^2(n-8) + \cdots + 3^{n/4}(0) = O(3^{n/4}).
$$
There are in fact closed formulas for this kind of sum (try Wolfram alpha), but you can also try to bound without them, say by looking at ratios of consecutive terms and comparison to a geometric series:
$$
3^{n/4} \left(0 + 4\frac{1}{3} + 8\frac{1}{9} + 12\frac{1}{27} + \cdots \right) = O(3^{n/4}),
$$
since the infinite series $4\sum_{m=0}^\infty \frac{m}{3^m}$ converges.


How can Lagrange Multipliers and Penalty Method be applied to optimize algorithms?

This technique is called Lagrangian relaxation.

The regular $DP$ approach, where $DP[a][b]$ represents the length of the longest increasing subsequence that ends in the $a$'th number and restarts at most $b$ times, is $\mathcal{O}(nk \log n)$. For convenience we'll assume the last number is the largest, and therefore $DP[n][k]$ is the value we are looking for (if this isn't the case, append $\infty$ and after calculating the answer decrement it by $1$).

To optimize this, we'll select some $\lambda \in \mathbb{N}$ which represents the cost of every exception, and compute $DP'[a] = \max_{b} DP[a][b] - \lambda b$. This can be done in $\mathcal{O}(n \log n)$: first sort the values, and keep a range maximum data structure over them, with all positions $j$ initialised to $v_{j} = 0$. Assume the value at position $i$ is the $p_{i}$th in the sorted list of values. Then $DP'[i] = \max(1 + \max_{j < p_{i}} v_{j}, 1 - \lambda + \max_{j > p_{i}} v_{j})$, and we set $v_{p_{i}} = DP'[i]$.

What use is computing $\max_{b} DP[n][b] - \lambda b$ to us? Notice that as we increase $\lambda$, the optimal $b$ in the maximum cannot increase. Similarly as we decrease $\lambda$, the optimal $b$ cannot decrease. If $\lambda = 0$, it is optimal to take all elements to our subsequence, and if $\lambda = n$, it is optimal to have $0$ exceptions. If we can find $\lambda$ for which the optimal $b$ can be $k$, then $DP[n][b] = DP'[n] + \lambda b$. Further, if such $\lambda$ exists, we can do binary search for it, yielding a $\mathcal{O}(n \log^{2} n)$ algorithm.

Note that we can modify the $\mathcal{O}(n \log n)$ algorithm to calculate the minimum and maximum values of $b$ that achieve the maximum value with the specific $\lambda$ with no increase in complexity. We can always find a $\lambda$ for which $\min_{b} \leq k \leq \max_{b}$, but this doesn't guarantee that there exists some subsequence with $k$ exceptions achieving the maximum. However, if we can show that $DP[n][b]$ is concave, i.e. $DP[n][b+2] - DP[n][b+1] \leq DP[n][b+1] - DP[n][b]$, we get this result, as we know that $DP[n][\min_{b} + 1] \leq DP[n][\min_{b}] + \lambda$ (due to maximality), therefore $DP[n][\max_{b}] \leq DP[n][k] + (\max_{b} - k) \lambda$, hence $DP'[n] = DP[n][\max_{b}] - \lambda \max_{b} \leq DP[n][k] - \lambda k$ and there exists a subsequence with $k$ exceptions achieving the maximum.

EDIT: Here is a C++ program for finding a maximal subsequence in $\mathcal{O}(n \log^{2} n)$. I use a segment tree for the range maximum data structure.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int INF = 2 * (int)1e9;

pair<ll, pair<int, int>> combine(pair<ll, pair<int, int>> le, pair<ll, pair<int, int>> ri) {
    if (le.first < ri.first) swap(le, ri);
    if (ri.first == le.first) {
        le.second.first = min(le.second.first, ri.second.first);
        le.second.second = max(le.second.second, ri.second.second);
    }
    return le;
}

// Specialised range maximum segment tree
class SegTree {
    private:
        vector<pair<ll, pair<int, int>>> seg;
        int h = 1;

        pair<ll, pair<int, int>> recGet(int a, int b, int i, int le, int ri) const {
            if (ri <= a || b <= le) return {-INF, {INF, -INF}};
            else if (a <= le && ri <= b) return seg[i];
            else return combine(recGet(a, b, 2*i, le, (le+ri)/2), recGet(a, b, 2*i+1, (le+ri)/2, ri));
        }
    public:
        SegTree(int n) {
            while(h < n) h *= 2;
            seg.resize(2*h, {-INF, {INF, -INF}});
        }
        void set(int i, pair<ll, pair<int, int>> off) {
            seg[i+h] = combine(seg[i+h], off);
            for (i += h; i > 1; i /= 2) seg[i/2] = combine(seg[i], seg[i^1]);
        }
        pair<ll, pair<int, int>> get(int a, int b) const {
            return recGet(a, b+1, 1, 0, h);
        }
};

// Binary searches index of v from sorted vector
int bins(const vector<int>& vec, int v) {
    int low = 0;
    int high = (int)vec.size() - 1;
    while(low != high) {
        int mid = (low + high) / 2;
        if (vec[mid] < v) low = mid + 1;
        else high = mid;
    }
    return low;
}

// Finds longest strictly increasing subsequence with at most k exceptions in O(n log^2 n)
vector<int> lisExc(int k, vector<int> vec) {
    // Compress values
    vector<int> ord = vec;
    sort(ord.begin(), ord.end());
    ord.erase(unique(ord.begin(), ord.end()), ord.end());
    for (auto& v : vec) v = bins(ord, v) + 1;

    // Binary search lambda
    int n = vec.size();
    int m = ord.size() + 1;
    int lambda_0 = 0;
    int lambda_1 = n;
    while(true) {
        int lambda = (lambda_0 + lambda_1) / 2;
        SegTree seg(m);
        if (lambda > 0) seg.set(0, {0, {0, 0}});
        else seg.set(0, {0, {0, INF}});

        // Calculate DP
        vector<pair<ll, pair<int, int>>> dp(n);
        for (int i = 0; i < n; ++i) {
            auto off0 = seg.get(0, vec[i]-1); // previous < this
            off0.first += 1;

            auto off1 = seg.get(vec[i], m-1); // previous >= this
            off1.first += 1 - lambda;
            off1.second.first += 1;
            off1.second.second += 1;

            dp[i] = combine(off0, off1);
            seg.set(vec[i], dp[i]);
        }

        // Is min_b <= k <= max_b?
        auto off = seg.get(0, m-1);
        if (off.second.second < k) {
            lambda_1 = lambda - 1;
        } else if (off.second.first > k) {
            lambda_0 = lambda + 1;
        } else {
            // Construct solution
            ll r = off.first + 1;
            int v = m;
            int b = k;
            vector<int> res;
            for (int i = n-1; i >= 0; --i) {
                if (vec[i] < v) {
                    if (r == dp[i].first + 1 && dp[i].second.first <= b && b <= dp[i].second.second) {
                        res.push_back(i);
                        r -= 1;
                        v = vec[i];
                    }
                } else {
                    if (r == dp[i].first + 1 - lambda && dp[i].second.first <= b-1 && b-1 <= dp[i].second.second) {
                        res.push_back(i);
                        r -= 1 - lambda;
                        v = vec[i];
                        --b;
                    }
                }
            }
            reverse(res.begin(), res.end());
            return res;
        }
    }
}

int main() {
    int n, k;
    cin >> n >> k;

    vector<int> vec(n);
    for (int i = 0; i < n; ++i) cin >> vec[i];

    vector<int> ans = lisExc(k, vec);
    for (auto i : ans) cout << i+1 << ' ';
    cout << '\n';
}

EDIT2: Thanks to Jaehyun Koo over at Codeforces I now know how to show concavity. The following is a modified version of his proof.

Consider the array partitioning problem. In it we are given values $cost[A][B]$ representing the cost of interval $[a, b)$, and wish to partition the array into intervals $[0, x_{1}), [x_{1}, x_{2}), \dots, x_{k}, n)$. Let $DP[n][k]$ denote the maximum sum $\sum_{i = 0}^{k} cost[x_{i}][x_{i+1}]$, where $x_{0} = 0$, $x_{k+1} = n$. We claim that $DP[n][k]$ is concave if the costs are Monge, that is, for all $a \leq b \leq c \leq d$ we have $cost[a][d] + cost[b][c] \leq cost[a][c] + cost[b][d]$.

First we'll show that our problem is an instance of the array partitioning problem with Monge costs. Set $cost[a][b]$ to be the length of the longest increasing subsequence in the interval $[a, b)$. Then $DP[n][k]$ for this instance of the array partitioning problem equals $DP[n][k]$ for our longest increasing subsequence problem. It remains to show that the costs are Monge.

Choose $a \leq b \leq c \leq d$, and take any LIS $L_{a, d} = x_{1}, \dots, x_{cost[a][d]}$ in the interval $[a, d)$, and any LIS $L_{b, d} = y_{1}, \dots, y_{cost[b][c]}$ in the interval $[b, c)$. We will combine them into two increasing subsequences in the intervals $[a, c)$ and $[b, d)$ of equal total length. To do this, let $x_{i}$ be the first $x$ and $x_{j}$ be the last $x$ in $[b, c)$. If $x_{i} \leq y_{1}$, set $L_{a, c} = (x_{1}, \dots, x_{i-1}, y_{1}, \dots, y_{cost[b][c]})$, $L_{b, d} = (x_{i}, \dots, x_{cost[a][d]})$. If $x_{j} \geq y_{cost[b][c]}$ do the same reversed. Otherwise, exists some $t, h$ s.t. $y_{h} \leq x_{t} \leq y_{h+1}$. Then set $L_{a, c} = (x_{1}, \dots, x_{t}, y_{h+1}, \dots, y_{cost[b, c]})$ and $L_{b, d} = (y_{1}, \dots, y_{h}, x_{t+1}, \dots, x_{cost[a, d]})$. Hence our cost array is Monge.

Now we'll show that the array partitioning problem with Monge cost is concave. Note that $DP[n][k+2] - DP[n][k+1] \leq DP[n][k+1] - DP[n][k]$ is the same inequality as $DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$. Take any partitions $x_{0}, \dots, x_{k+3}$ and $y_{0}, \dots, y_{k+1}$ with values $DP[n][k+2]$ and $DP[n][k]$ respectively. Take any $0 \leq i \leq k$ such that $y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$. Such $i$ always exists, as some interval $[y_{i}, y_{i+1}]$ must be the first such that the last $x$ before the end of the interval, $x_{j+2} \leq y_{i+1}$ has $j \geq i$, thus $x_{i+2} \leq x_{j+2} \leq y_{i+1}$ and $y_{i} \leq x_{i+1}$ as otherwise the interval $[y_{i-1}, y_{i}]$ would contain $x_{i+1}$ contradicting the minimality of $i$.

We make the partitions $y_{0}, \dots, y_{i}, x_{i+2}, \dots, x_{k+3}$ and $x_{0}, \dots, x_{i+1}, y_{i+1}, \dots, y_{k+1}$, both of length $k+1$. What is the difference in total value? Most terms cancel, but in the sum of values of the original we have $cost[x_{i+1}][x_{i+2}]$ and $cost[y_{i}][y_{i+1}]$, while in the new one we have $cost[y_{i}][x_{i+2}]$ and $cost[x_{i+1}][y_{i+1}]$. But since $y_{i} \leq x_{i+1} \leq x_{i+2} \leq y_{i+1}$, by the Monge property $cost[y_{i}][y_{i+1}] + cost[x_{i+1}][x_{i+2}] \leq cost[y_{i}][x_{i+2}] + cost[x_{i+1}][y_{i+1}]$, hence the total value can only increase, and $DP[n][k+2] + DP[n][k] \leq 2 DP[n][k+1]$.


I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list than a set indeed ---thought sets might be used as well, see below.

Anyway, your understanding of the purpose of the OPEN list is perfect. It should contain all nodes generated that are awaiting for expansion, in contraposition to the so-called CLOSED list that contains all nodes that have been already expanded.

There are many different implementations of the OPEN list. For a good review of different ways to implement it, see Chapter 3 of Stefan Edelkamp, Stefan Schroedl Heuristic Search: Theory and Applications, Morgan Kaufmann 2011. In the following I'm just describing three typical alternatives:

Plain open list

The first alternative consists simply of using a list which sorts nodes in ascending order of their $f$-value. Extracting nodes from the list is done in $O(1)$ as it just suffices to take the first item from the list. Inserting is a little bit more difficult. The best would consist of creating a small OPEN list with the descendants of a node that has just been expanded and to sort it in ascending order of their $f$-values. Next, merge this sort list with the global OPEN list. The operation has a cost which is logarithmic in the size of the global OPEN list, but be aware that its size grows exponentially.

Bucketed open list

If the $f$-values of all nodes are known to be discrete and also to be bounded by a constant $B$, then create an array with $(B+1)$ locations, each one pointing to one different list. This ensures that inserting nodes in the OPEN list takes only $O(1)$: given a node with an $f$-value equal to $x$, just add it to the tail of the list pointed to by location OPEN[x]. Extracting is a little bit more difficult, but still very easy. You have to keep track of the lower non-empty index $x$, min x. When popping a node return the first node in the list pointed to by OPEN[min x]. Clearly, this requires some maintanenance: first, when removing all nodes with an $f$-value equal to min x, it is necessary to update this lower bound; secondly, if a node with an $f$-value strictly less than the current min x is inserted, min x has to be updated as well.

Using sets

A$^*$ might additionally require to perform searches in the OPEN list. Strictly speaking, this is not required and the only purpose for doing it is to save some memory ---which anyway will grow exponentially. Note please that this will not avoid redundant expansions, as the CLOSED list already serves specifically to that purpose (in a nutshell: before the expansion of any node verify it is not in the CLOSED list; if so, skip the current expansion; otherwise, expand it and insert it into CLOSED) so I do not think it is really common practice to avoid the insertion of nodes in OPEN that are already in OPEN.

Anyway, if you are interested in saving some additional memory at the expense of investing some additional CPU running time, create a set with the current contents of the OPEN list (implemented in either way) and use it only for performing searches. Yeap, you might be thinking that you are then using twice the memory required by A$^*$ but be aware that the memory consumption of this algorithm is exponential in the depth of the paths generated, so that multiplying the memory usage by a low constant (such as two) will not prevent your algorithm from finding solutions that otherwise could have been found.

Hope this helps,


Computing follow sets conservatively for a PEG grammar

Follow or lookahead sets are a standard concept in compiler theory. I would expect every textbook on the topic to contain an algorithm for them; as for online resources, try this or  that one. It seems as if the choice of algorithm depended on what kind of grammar -- LL, LR, LALR, ... -- you have.


Given the Equivalence relation R = { x, y $\in$ $\Bbb{Z}$ : (x+y) mod 2 = 0}, what are equivalence classes 1 and 2?

There is no general way to answer such a question other than to repeat the definition. So one might answer for example for $1$:

  The equivalence class that $1$ belongs to is the set of all integers $n$ such that $1 + n \equiv 0 \mod 2$.

You might simplify this by noting that $1 + n \equiv 0$ implies $n \equiv 2-1$ or $n \equiv 1$ modulo $2$, giving:

  The equivalence class that $1$ belongs to is the set of all integers $n$ such that $n \equiv 1 \mod 2$.

Now the answer that the asker is looking for will probably be "the odd integers". If they disagree that the above answer is correct I would argue that the question is too vague however, as in my view the above is perfectly correct.


For what special cases does this vertex cover algorithm fail or work?

Trying to take "high priority" i.e. high degree vertices over their neighbors will not work in all cases. This algorithm chooses $n-1$ for $C_n$ (Cycle Graph on $n$ vertices). It should choose either $(n-1)/2$ or $n/2$ if its odd or even. It also fails for Perfect Graphs.

I'm pretty sure this gives a $O(\log n)$ approximation too. If you order vertices by degree and greedily select vertices until all edges are covered, it is basically the same greedy algorithm as $O(\log n)$ set cover.


How to compute all primes between upto $n$ in time $O(n)$ time?

You can use a sieve to enumerate all prime numbers up to $n$.  There are multiple algorithms; see the Wikipedia article I link for some examples.  The sieve of Atkin and wheel sieves apparently run in $O(n)$ time.


If P is equal to NP, then what happens to the problems those can be solved in polynomial time?

First of all, it is not clear what you mean by an algorithm which is able to solve any problem in NP; usually one algorithm solves one problem. However, given a polynomial time algorithm for solving some NP-complete problem, you can solve any NP problem in polynomial time. However, every problem will require a different algorithm.

This doesn't necessarily affect problems which are already in P. Indeed, we have unconditional lower bounds on search and sort which show that no $O(n)$ sort or $O(\log^* n)$ search algorithm exist, in restricted computation models. Even when tight bounds are not available (or when you consider a computation model for which good lower bounds are not available), there is no reason to assume that an algorithm for NP-complete problems is relevant.

On the other hand, if P=NP then more difficult problems are affected: you can show using a padding argument that P=NP implies EXP=NEXP, for example. But the implication doesn't go the other way around.