Solving second-order ODEs with Taylor series approximation of second derivative and linear algebra I was told about an algorithm to solve ODEs which I thought was very clever. I am sure its not something new. It works by discarding the $\mathcal{O}(h^2)$-term from the usual formula for computing the second derivative:

$$f''_i = \frac{f_{i-1} + f_{i+1} - 2f_{i}}{h^2} + \mathcal{O}(h^2), \qquad i = 0,1,2,\cdots,N$$

one can rewrite the equations for the derivatives for all $i$, as a set of linear equations, then use smart Gauss elimination from linear algebra to find expression for $f$ with exactly $5N$ floating point operations.

(1) Does this method already have a name?

(2) Should I be excited about this algorithm? Is this a particularly good method? Or are there other very different algorithms for solving ODEs which are much better?

What you have there is the central difference approximation to the second derivative. The Wikipedia article on finite differences explains this pretty well.

Of course, this isn't a method as such; that depends on the exact problem being solved. If this were an initial value problem, then a simple rearrangement of this equation is typically known as Störmer–Verlet integration (or just Verlet integration depending on whom you ask).

If it was a bounding-value problem, then this discretisation of the derivative gives you a tridiagonal system, and you don't have a complete "method" until you have a method to solve it. A small modification of Gaussian elimination is quite efficient on matrices of this form.

As to competitors... that's a very long discussion. Any introductory textbook on numerical analysis should give you a good start.


How does the Program Counter work? I think it stores the address of the current instruction. And if this instruction is completed the program counter is incremented by 1, to get the next instruction.
But now my question is, how do you increment the program counter by 1? It would mean you increment an address by 1, how does this work?

Assuming a 32-bit architecture (with alignment), then instructions are words; that is, every instruction is composed of 4 bytes.

That implies that the bottom two bits of the address are byte offsets within the word; that is, the address 10001111 denotes 4th byte of the word at 10001100. When we're talking about instructions, however, we'll never need to fetch individual bytes -- we want whole words.

Different textbooks handle the program counter differently, but given that whichever paradigm you're using has the program counter incremented by 1 (rather than 4), that leads me to believe that the PC stores word address, rather than byte address.

Then, if the program counter is at 10001111 and we increment by 1, we do in fact get 10010000. To turn this word address into a byte address (so we can fetch the instruction from memory), we can simply left-shift by 4.

In short, if the program counter is at 10001111 (the word address), then the byte address of the instruction we'll actually be fetching is 1000111100. To fetch the next instruction, we can just increment the program counter by 1.


Prove that a DFA will transition to the same state after $\gcd(i,j)$ steps where $i$ and $j$ steps can be taken to reach that state Suppose $M=(Q,\Sigma,\delta,q_0,F)$ is a deterministic finite automaton, and suppose there exists a state $q \in Q$, a string $z \in \Sigma$, and integers $i,j>0$ such that $\delta(q,z^i)=\delta(q,z^j)=q$. Prove that $\delta(q,z^{gcd(i,j)})=q$

I can intuitively say that starting from a state $q$ if you take $x$ steps on a DFA to reach the same state and at the same time $y$ steps also takes the DFA to the same state, then there exists a cycle that is repeated $\gcd(x,y)$ times to reach the same state again and again. Is this correct for a DFA? How can I prove this formally?

Consider the sequence $q(n) = \delta(q,z^n)$ for $n \geq 0$. Let $b$ be the smallest index so that $q(a) = q(b)$ for some $a < b$. It is not hard to check that all further iterates cycle through the values $q(a),\ldots,q(b-1)$. Since we are given that $q(i) = q(0)$, it follows that $a = 0$, and so the function $\pi$ on $\{q(0),\ldots,q(a-1)\}$ defined by $\pi(q') = \delta(q',z)$ is a cyclic permutation.

We are given that $\pi^i(q) = \pi^j(q) = q$. Since $\pi$ is a permutation, also $\pi^{-i}(q) = \pi^{-j}(q) = q$. It follows that for any integer $\alpha,\beta$ (not necessarily non-negative) $\pi^{\alpha i + \beta j}(q) = q$. In particular, Bezout's identity shows that $\pi^{\operatorname{gcd}(i,j)}(q) = q$, and so $\delta(q,z^{\operatorname{gcd}(i,j)}) = q$.


Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average? I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average case.

However, I think, if such algorithms can exist, there are more than one of them.

Anyway, what I want to know if there is any known algorithm with restrictions given in title.

Note. It must be appliable to simple arrays without repeatitions (no precomputing/hashing).

Yup.  Do interpolation search, but after $\log n$ iterations, if you haven't found the answer yet, switch to binary search.  This ensures a $O(\log n)$ worst-case running time, while retaining the $O(\log \log n)$ average-case running time.  Note that the average case only applies if you make a particular assumption about the distribution of values in the array.


Restricting longest path with 2-coloring to paths of at most constant length I am trying to create a polynomial time algorithm for a problem defined as follows:

c-ZPath(cZP)
$c$ is an integer constant $\geq 1$
Input: An undirected graph $G=(V,E)$.
Question: Can the vertices in $G$ be colored with two colors such that

no edge’s endpoint vertices have the same color and

there is a path in this colored version of $G$ with $\geq c$ edges in which no vertex or edge repeats and the vertex-colors alternate for the entire length of the path?

I understand that the coloring can be checked by a simple breadth first search in polynomial time.
My problem is with the path of length $c$. My professor stated that the reason that this is not NP-complete and analogous to the longest path problem is because $c$ is a constant. I fail to see why this restriction causes it to differ from longest path. If anyone could clarify this for me I'd be really greatful.

If you want to check whether a graph has a path of length $c$, you can go over all ordered sequences of $c+1$ vertices, and check whether all the edges in the corresponding path exist. On a RAM machine, this is an $O(n^{c+1})$ algorithm. When $c$ is constant, this is polynomial time.


Portfolio rebalancing algorithm Quite possibly this problem is already solved and has it's own name, but I was unable to find any directions.

So, I have a portfolio with some items in it:

| Name   | Price | Amount | Share |
|--------|-------|--------|-------|
| Item 1 | 200   | 1      | 25%   |
| Item 2 | 100   | 2      | 25%   |
| Item 3 | 50    | 4      | 25%   |
| Item 4 | 25    | 8      | 25%   |

After some time, prices changed

| Name   | Price | Amount | Share  |
|--------|-------|--------|--------|
| Item 1 | 220   | 1      | 27.36% |
| Item 2 | 130   | 2      | 32.34% |
| Item 3 | 17    | 4      | 8.46%  |
| Item 4 | 32    | 8      | 31.84% |

but I still want all items to have 25% share.

Assuming amount can be decimal, how do I find the optimal way of rebalancing this portfolio back to 25% shares? How to determine how many of each item to sell so we won't have to buy it back again (sell everything and spend 25% on each item is not an option)?

What if I have extra $100 to spend while rebalancing?

Upd: what I mean by "optimal" is to keep the amount of transactions as less as possible, assuming each transaction costs something.

Your problem specification is incomplete. What do you mean by optimal? Do you want to, say, minimize transactions costs? Do you want to make sure you do not cross the spread?

The original portfolio was worth \$800. The new portfolio is worth \$804. Assuming your actions do not change the market price, and assuming no transactions costs, that is a given.

You had \$200 allocated to each security. Now, you want \$201 allocated to each security:

| Name   | Price | Amount | Notional |
|--------|-------|--------|----------|
| Item 1 | 220   | 1      |  $220    |
| Item 2 | 130   | 2      |  $260    |
| Item 3 | 17    | 4      |   $68    |
| Item 4 | 32    | 8      |  $256    |

For every security whose notional is above the desired amount, sell that many units:

Item 1: Sell 19/220 = 0.0863636363636364 units
Item 2: Sell 59/130 = 0.453846153846154 units
Item 4: Sell 55/32 = 1.71875 units

With the money you made from those sales, i.e. \$19 + \$59 + \$55 = \$133, buy 7.82352941176471 units of Item 3.

Now, you will have \$201 worth of each security, exactly 25% of the new portfolio size of of \$804.

The only time the extra \$100 would come in to play is if you are trying to minimize your transaction costs and/or if you are worried about not being able to trade at the spot etc.

With the extra \$100, you want to allocate \$226 to each security. So, buy 6/220 units of Item 1, buy 158/17 units of Item 3, and sell 34/130 units of Item 2 and 30/32 units of Item 4.

However, as far as I can see, you have not specified an optimization problem.

Let $c_i$ denote current units of security $i$ in your portfolio. Let's say you pay a percentage commission of $k$ per transaction. The amount you buy of security $i$ is denoted $x_i$ (negative $x_i$ mean selling). Your objective function is to minimize $\sum_i k p_i |x_i|$.

Since $k$ is a constant, this is equivalent to minimizing $\sum_i p_i|x_i|$ where $|x_i|$ is the absolute value of $x_i$.

This objective is subject to the portfolio allocation constraints:

$p_1(c_1 + x_1) = p_2(c_2 + x_2)$
$p_2(c_2 + x_2) = p_3(c_3 + x_3)$
$p_3(c_3 + x_3) = p_4(c_4 + x_4)$.

Further, the new value of your portfolio, $\sum_ip_i(c_i + x_i)$, plus the amount you spend, $k\sum_ip_i|x_i|$, must be affordable, i.e, must be less than or equal to $B + \sum_ip_ic_i$ which is the current value of your portfolio and the additional balance you have available.

This, of course, ignores borrowing money to finance the rebalancing which might be worthwhile depending on borrowing costs.

I am assuming there is going to be no short selling in a portfolio rebalancing, so $x_i>-c_i$ must also hold.

You might be able to simplify the problem, and possibly save some money, by first spending $B$ on underbought items.

You might be able to drop the absolute values by first deciding which stocks are overbought.

I did not prove the last two statements.

When I get a chance, I will post the solution to the applicable linear program.


Can you give an inductive definition to define the length of a list L? Having trouble understanding what it means to define something inductively in the following context.

  Can you give an inductive to define the length of a list L?

  a. The total number of items in L is the length of L

  b. Basis: the length of an empty list is 0
  Induction: the length of a list is 2*(length of half the list)

  c. Basis: the length of an empty list is 0
  Induction: the length of a list is (length of head(list))+(length of tail(list))

  d. Basis: the length of an empty list is 0
  Induction: the length of a list is 1+(length of tail(list))

The answer is (d). Why might this be?

And also for this similar question:

  Can you give an inductive definition to define what it means for an element X to
  be a member of a list L?

  a. X is a member of a list L if and only if X belongs to the list L.

  b. X is a member of a list L if either X is the head of the list or X is a member of the tail of L.

  c. X is a member of a list L if we can find an element Y in L and X=Y.

  d. X is a member of a list L if we can find an element Y in the tail of L

The answer is (b).

Thank you.

In an inductive definition what you have to do is to find a base case and the inductive step.

In your case, suppose to have a list $L$ and let head be the first element and tail the rest of the list.

For example, if $L=[1,2,3,4,5]$:

head = $1$
tail = $[2,3,4,5]$

In order to understand the meaning you could consider writing a recursive function to compute the length of the list.

According to the answer

Basis: the length of an empty list is 0
Induction: the length of a list is 1+(length of tail(list))

This corresponds to the recursive function

function len(list L)
   if L is empty
        return 0
   else return 1 + len(tail(L))

Same for the second question:

function member(elem x, list L)
   if L is empty
       return false
   if head == x
       return true
   else return member(x, tail(L))

and this corresponds to say: X is a member of a list L if either

X is the head of the list or
X is a member of the tail of L.


Scala as a language for Generic Programming I posted the same Q at programmers.SE, but nobody really helps.

In the paper “An Extended Comparative Study of Language Support for Generic Programming” by Garcia et al. an interesting comparison of programming languages features for generic programming is given:

with the brief explanation of terminology:

Can anyone assess Scala programming language support for generic programming in a view of this framework? I.e. add a column in the first table with explanations and examples if possible.

Exact answer is given on p. 17 of “Type classes as Objects and Implicits” by Oliveira et al.


Sorting a stack of cards with help of a computer I have a physical stack of cards, with numbers on them (or, in reality, I have a stack of exams, with students names on them ;)). I want to sort the cards in ascending order.

This is an extremely boring task. I usually use mergesort myself (quick question: what do you use?). But say each card has a QR code. I can scan all the codes as I go through the stack using my mobile phone and then I have the list of cards and the order in which they appear.

What would be a clever way to use this information in order to tell a human how to sort the stack of cards? I imagine that the computer could somehow give me instructions of what to do so as to arrive at the sorted order. Notice that things like "take the 52nd card and place it on the top" are not nice, since I don't want to count to the 52nd card. What would you do?

I realize this question is rather subjective: what constitutes a "nice" strategy depends on the person. I just want to know what kinds of ideas you people could come up with.

Setup an array of initially empty file folders (even better buy a mail sorter and you are in the pigeonhole sort case).
The computer, knowing the initial order of the cards, will tell you, one by one, where to put each card (you have a limited number of folders so instructions like "take the current card and place it on top / bottom of folder 3" are quite easy to follow).
Manually sort each non empty folder using insertion-sort.
Visit the folders in order and put all cards back onto the table.

(repeat n times and you're ready for the parcel delivery office, almost... a railway post clerk was required to sort 600 pieces of mail in an hour with 97% accuracy in order to keep his job :-)


What is Temperature in LSTM (and neural networks generally)? One of the hyperparameters for LSTM networks is temperature. What is it?

Temperature is a hyperparameter of LSTMs (and neural networks generally) used to control the randomness of predictions by scaling the logits before applying softmax. For example, in TensorFlow’s Magenta implementation of LSTMs, temperature represents how much to divide the logits by before computing the softmax.

When the temperature is 1, we compute the softmax directly on the logits (the unscaled output of earlier layers), and using a temperature of 0.6 the model computes the softmax on $\frac{logits}{0.6}$, resulting in a larger value. Performing softmax on larger values makes the LSTM more confident (less input is needed to activate the output layer) but also more conservative in its samples (it is less likely to sample from unlikely candidates). Using a higher temperature produces a softer probability distribution over the classes, and makes the RNN more “easily excited” by samples, resulting in more diversity and also more mistakes.

Neural networks produce class probabilities with logit vector $\mathbf{z}$ where $\mathbf{z} =$$(z_1,\ldots,z_n)$ by performing the softmax function to produce probability vector $\mathbf{q} = (q_1,\ldots,q_n)$ by comparing $z_i$ with with the other logits.

$q_i = \frac{\exp{(z_i/T)}}{\sum_j\exp{(z_j/T)}}\tag{1}$

where $T$ is the temperature parameter, normally set to 1.

The softmax function normalizes the candidates at each iteration of the network based on their exponential values by ensuring the network outputs are all between zero and one at every timestep.

Temperature therefore increases the sensitivity to low probability candidates. In LSTMs, the candidate, or sample, can be a letter, a word, or musical note, for example:

  For high temperatures (${\displaystyle \tau \to \infty }$), all [samples] have nearly the same probability and the lower the temperature, the more expected rewards affect the probability. For a low temperature (${\displaystyle \tau \to 0^{+}}$), the probability of the [sample] with the highest expected reward tends to 1.

- from Wikipedia article on softmax function

Reference

Hinton, Geoffrey, Oriol Vinyals, and Jeff Dean. "Distilling the knowledge in a neural network." arXiv preprint arXiv:1503.02531 (2015). arXiv


NFA equality for automata with partial transition functions and all states accepting Given two nondeterministic finite state automata with partial transition functions, such that all states are accepting, except for the implicit failure sink state, is it possible to decide in polynomial time whether the two automata recognize the same language? Or is it perhaps PSPACE-hard, like the same problem for general NFAs?

The problem is PSPACE-complete, by reduction from the equivalence problem for NFAs.

Suppose we are given two NFAs $A_1,A_2$ over an alphabet $\Sigma$. Let $\dashv$ be a new symbol. To each of the NFAs we add two new states $q_f,q_t$, and the following transitions:

An $\epsilon$-transition from the initial state to $q_t$.
A self-loop on $q_t$ labeled $\Sigma$.
A transition labeled $\dashv$ from every accepting state to $q_f$.

Let $B_1,B_2$ be the new NFAs, after making all of their states accepting. Then
$$
L(B_i) = \Sigma^* \cup (L(A_i)\dashv).
$$
Therefore $L(A_1) = L(A_2)$ iff $L(B_1) = L(B_2)$.


Zero-knowledge proof of $\beta\eta$ equality Is there some way to give a zero-knowledge proof that two $\lambda$-terms are convertible, i.e. equal modulo $\beta\eta$?

A usual (and not zero-knowledge) proof that two terms are convertible is a path of terms between the two such that each step is either a single $\beta$ reduction or a single $\eta$ expansion, or the reverse of either one. Testing that two terms are convertible is only semi-decidable because no bound can be given a priori on the length of that path.

The question is the following: Alice has two $\lambda$-terms $t_1$ and $t_2$, and a proof that they are convertible. Can she convince Bob that they are convertible without helping Bob find the path?

One way to do this would be that Alice gives Bob a third term $t_3$ that she knows is convertible to the two others, and then Bob gets to ask her either to prove that it's convertible to $t_1$ or that it's convertible to $t_2$. I'm not sure how the term $t_3$ can be chosen though.

I doubt that a zero-knowledge proof is possible, because it seems likely that any finite proof will leak at least partial information about the length of the path that converts $t_1$ to $t_2$, and hence won't be zero-knowledge.  In particular, suppose Alice and Bob's interaction takes $T$ time steps.  Then in any reasonable proof I can imagine, Bob would be able to infer that $t_1$ can be converted to $t_2$ using a path of length at most $T$.  This is partial knowledge, because there exists a pair $t_1,t_2$ of terms that take strictly more than $T$ time steps to convert.

I suspect that we might need an additional condition, such that there is a fixed and known upper bound $B$ on the length of the path converting $t_1$ to $t_2$.  If you have such a bound, there is a zero-knowledge proof protocol whose complexity is polynomial in $B$, as the statement you are proving becomes a NP-statement, and it is known that there are zero-knowledge protocols for every language in NP.


Christofides algorithm (by hand) (suboptimal solution - is it my fault?) I would like to calculate an eularian path using Christofides algorithm on this graph: (Focus on the first number in each box representing the distance)

$\alpha$ denotes the start and end vertex of the Eulerian path

Step 1 - Calculate minimum spanning tree $T$

Step 2 - Calculate the set of verices $O$ with odd degree in $T$

Step 3 - Form the subgraph of $G$ using only the vertices of $O$

This is starting to get confusing

Step 4 - Construct a minimum-weight perfect matching $M$ in this subgraph

Step 5 - Unite matching and spanning tree $T$ and $M$ to form an Eulerian multigraph

I am NOT satisfied

Did I do something wrong or did I simply just hit an sub-optimal solution.
It is not hard to see that the Eulerian path easily could be improved by either connection $G \rightarrow H$ or $A \rightarrow B$ as illustrated underneath:

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of

On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$\alpha$ should be replaced by edge HG.


Finding the last substring in lexicographical order in O(n) time Given a string s, return the last substring of s in lexicographical
  order.

  Example 1:

  Input: "abab" Output: "bab" Explanation: The substrings are ["a",
  "ab", "aba", "abab", "b", "ba", "bab"]. The lexicographically maximum
  substring is "bab".

More specifically, I am looking for an accompanying proof/intuition. I can find many solutions, but none provide a proof of their technique and I cannot convince myself.

source: https://leetcode.com/problems/last-substring-in-lexicographical-order/

Consider a string of 100 million characters with say 100 z’s in between plus a huge number of the characters a to y (and no character lexicographically after z). Find an algorithm that would often give you the correct result in O(n), actually with at most 2n comparisons. Find out why this algorithm doesn’t always run in O(n), then figure out what you can do about it to still run in O(n). For example, if you have a million repetitions of zabcdefabcdef.


Efficient lookup when key is made of multiple elements and elements can be empty I am wanting to create a map where the key contains multiple elements and the elements can be empty/null. The empty values are treated as "anything". I want to lookup function to match when the stored key is the lookup value or it is a generalised version - index key has empties where lookup value has values. I think the formalisation would be "the lookup value logically subsumes the index-key". I also want the lookup function to return the most specific index-key, that is the key with the fewest empties.

For example, if the data is stored in a (<key>, <value>) tuple with the key being a tuple of the elements and ? representing the empty set/null value:

((1, ?, 6, 3), "hey")
((1, 5, 6, 3), "hi")
((2, ?, ?, ?), "hello")

So lookup((2, 4, 5, 6)) -> "hello". And lookup((1, 5, 6, 3)) -> "hi" because (1, 5, 6, 3) is more specific than (1, ?, 6, 3).

A simple solution is to store them as shown above and simply look through them. This would take $O(nm)$ where $n$ is the number of entries and $m$ is the number of elements in the key. Checking in most-to-least specific would mean a match could be returned immediately.

This there an approach that could improve this?

Thank you

This is the problem of building a data structure for storing rectangles in $m$-dimensional space, so you can answer stabbing queries efficiently.

For instance, if your keys have 4 elements, then we are in $m=4$ dimensions.  The key $(1,5,6,3)$ corresponds to a single point in 4-dimensional space.  The key $(1,?,6,3)$ corresponds to a line in 4-dimensional space.  The key $(2,?,?,?)$ corresponds to an (infinite) box in 4-dimensional space.

So, in general, each key can be thought of as an (axis-aligned) box in $m$-dimensional space.  A query is a point in $m$-dimensional space, and you want to find all boxes that contain that point.  That is sometimes known in the literature as a "stabbing query" (particularly when we're talking about intervals, i.e., $m=1$).

There are many data structures for this problem.  Take a look at R-trees, for example.  You can also look at $m$-dimensional segment trees.  It is known that you can build a $m$-dimensional segment tree in $O(n (\lg n)^m)$ time and $O(n (\lg n)^m)$ space; each lookup can be answered in $O(k + (\lg n)^m)$ time, where $k$ is the number of entries that match the query.  Thus, segment trees will likely be a good representation if the dimension $m$ is small.  (Optimizations: The exponent can be reduced slightly from $m$ to $m-1$.  There are also special algorithms that achieve even better performance in the case of $m=2$, $m=3$, or $m=4$.)

See also Data structure to hold list of rectangles?.


How to get all in constant time? We are planning to design a system where following operations are supported.

Increment("foo"): Increase the count of key 'foo'

Decrement("bar"): Decrease the count of key 'bar'

getMin():  Return the key which has minimum count

getMax():  Return the key which has maximum count

The catch is all operations should be in $O(1)$ time.

If your keys are strings, you can use a prefix tree mapping keys to values. In this way each operation can be implemented in $O(h)$ time, where $h$ is the length of the key, which means it is $O(1)$ to the size of the collection.
To get the minimum key(or maximum) you can traverse the tree, by going through the edge from the lexicographically smallest (or largest if you need max) node on each level.
 I don't think you can get better complexity than $O(h)$ for arbitrary sized keys as you need $O(h)$ time to output the key anyway.


What to do following a reduce in LR(1) parsing? I am using this standard question from Dragonbook as an example, (the first problem) . I have trouble with what happens in State 4 on LR(1) parsing. Once it is reduced by the rule C->d, now what will the current state be? It seems like it could be both State 0 or State 3 (since state 3 loops back on itself on the lookahead c), i.e the GOTO of C from either state 0 or state 3. I am confused on states like 3 that loop into themselves.
The grammar is this:
$$S'  \rightarrow  S $$
$$S  \rightarrow  CC $$
$$S  \rightarrow cC $$
$$C  \rightarrow d $$

Question 1 : When the machine is at state 3. On encountering d as a lookahead, what is the action, and the new state?
Question 2 : At a more fundamental level, what do you do following a reduce in any kind of LR parsing. You can't stay in that state itself, and have to go somewhere else right? How do you make that choice?
Edit: I made a small mistake in the grammar productions. I had originally included the grammar C -> c which was a mistake, and was removed.

It may help to think in terms of lookahead sets, rather than lookahead symbols. So the item set in state 4 is actually:
$$\left[ C \rightarrow d \cdot, \left\{ c, d \right\} \right]$$
According to the definition of a $LR(1)$ automaton, what you should do is look at the lookahead symbol. If it's $c$ or $d$, then reduce by $C \rightarrow d$, otherwise it's a parse error.
This is correct behaviour, and you would get full marks for this answer. However, it's not how $LR$ parser generators work in practice!
A grammar which is $LR(1)$ but not $LR(0)$ has a $LR(0)$ automaton which is correct. The problem is that it's nondeterministic. And, indeed, there are variants (e.g. $GLR$) which allow for nondeterministic automata.
What that means is that in practical applications, you don't need to consult the lookahead set if you don't need to in order to make a parsing decision.
In your case, state 4 does not need lookahead to disambiguate it. If you didn't bother looking at the lookahead set, and just reduced anyway, the parse error would be caught as soon as you tried to shift the next symbol, because there isn't a transition for it. Try parsing the string d$ to see what I mean.
Real-world grammars tend to produce $LR$ automata with a lot of these states where the only possible action is to reduce by a single production. So real-world parser generators tend to optimise them by not storing their lookahead sets. We call these $LR(0)$ reduce states.
In true $LR(k)$ parsing, you will often find $LR(0)$ reduce states which differ only in their lookahead sets:
$$\begin{eqnarray*}
q_1: & \,\, & \left[ A \rightarrow \alpha \cdot, \phi \right]\\
q_2: & & \left[ A \rightarrow \alpha \cdot, \psi \right]
\end{eqnarray*}$$
(Exercise: Why can this never happen in a $LALR(k)$ automaton?)
You can merge these states and the resulting automaton will still be correct, and will still be deterministic if the original automaton was deterministic.


Complexity of Hopcroft-Karp I have a rather basic question about the number of operations taken by the Hopcroft-Karp algorithm for finding a maximum matching in a bipartite graph. It is commonly reported as $O(m \sqrt{n})$ where $m$ is the number of edges in the graph and $n$ is the number of vertices(for example, see wikipedia or this book, among many examples - I cannot post more than two links due to reputation constraints).

What bothers me about this is that if $m$ is small (say $m=n^{1/4}$) this seems to require less than $n$ iterations, which is odd: surely you have to at least look at every node, i.e., just to see if it has any incident edges or not?

Having looked at Hopcroft and Karp's original paper, I see they quote a running time of $O((m+n)\sqrt{n})$ which makes more sense.

So my question is: what is the reason why the running time of Hopcroft-Karp is usually quoted as $O(m \sqrt{n})$? Does this reflect an assumption that the graph is connected (I never see this stated explicitly)?

The correct running time is indeed probably $O((m+n)\sqrt{n})$. However, this is a mouthful, and the expression $O(m\sqrt{n})$ looks nicer and is also more succinct. In most cases, $m \geq n/2$, since otherwise there is an isolated vertex. In fact, by finding isolated vertices, we can improve the running time of the algorithm to $O(n + m\sqrt{n})$.

An alternative way of stating the running time would be $O(m\sqrt{n})$, assuming $m \geq n$. The case of small $m$ is not so interesting (since then there are isolated vertices which can be eliminated), and so it is usually assumed that $m = \Omega(n)$.


Does pre-emption of a process occur when that process is busy waiting? I was reading about Peterson's Solution for Synchronisation. Let's assume the two shared variables to be int bool flag[2] and turn. Lets also consider the two processes as P0 and P1.

Initially, P0 executes causing - flag[0] = true and turn = 1. Now lets assume P0 is pre-empted by P1 causing - flag[1] = true and turn = 0

Now, busy waiting condition of P1

while(flag[0] == true && turn == 0);

puts P1 on an indefinite wait until P0 resumes its execution, completes it and turns flag[0] = false. But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ? So does a process pre-empt if it's busy waiting?

There are two broad concepts at play here: "synchronization" and "pre-emption". To make sure both processes run mutually exclusively, they first try to make sure the other one executes in the hope that in the future, the other process will ultimately unblock them by setting their respective flags.

To make sure both processes run to completion on this premise, the OS or any scheduler for that matter, should ensure that both processes are given their share on the CPU. Now coming to your question:

  So does a process pre-empt if it's busy waiting?

Yes, absolutely. If the scheduler (OS) upholds multi-tasking (say round-robin scheduling?) then the busy-waiting process will indeed pre-empt at some point in time. But keep in mind things get a little complicated when features like process priorities are added into play.

The other question:

  But wouldn't this again require P1 to be pre-empted, and bring back P0 from 'Ready' to 'Running' and get it executed ?

follows the answer to previous question that P1 would be pre-empted and eventually, P0 will run to completion thereby allowing P1 to also run to completion.

Final thoughts:

This is a basic synchronization primitive and a great example to help understand synchronization/mutual exclusion concepts. But, it doesn't take into account performance and busy-waiting is definitely not good performance-wise. There are other primitives that operate in post-wait fashion instead of busy-wait (Semaphores, for instance) which could be a better option.


Is my understanding of kernels correct? System: Application

OS: Scheduler, VMM, IPC, FS Drivers, dispatchers, VFS

The above would be a monolithic kernel. In a monolithic kernel all core OS functions are separate from user spaaaaaace. Functions such as the FS are handled completely by the kernel. This leaves the end user/dev open to write applications that rely solely on the kernel to emulate and process the functions. The BSD tree, AIX, and HP-UX are good examples of monolithic kernels.

System: Application

User Mode: Application IPC, Unix Server, Drivers, File Server

OS: Basic IPC, VMM, Scheduling

This is a microkernel. A microkernel is responsible solely for physical emulation of the machine code. It provides a more secure functionality, but also allows for better hardware processing. User spaaaaaace is where drivers are handled, sometimes grating DMA. Also, it can improve computing processing time if the user spaaaaaace is streamlined for direct machine emulation. JXOS and various nanokernels are good examples.

System: Application

User Mode: Drivers, Unix Server, Application IPC

OS: Microkernel, Kernel Drivers, IPC, HAL

This is a hybrid kernel. A hybrid kernel is mix between a monolithic kernel and a microkernel. Software drivers are handled in user mode, but hardware drivers are handled by the kernel. This allows for a lot of flexibility in design, as some packages and application functions can run directly against the kernel. However, this leaves the kernel open to a lot of security vulnerabilities. The most well-known hybrid kernel is Windows NT.

My architect was testing my knowledge of kernels, and this is what I sent him. He said that I wasn't wrong, I just have a very different approach to it. When interrogated about it, he just told me it was different. How is it different? Does it look different?

Right as far as it goes, but the differences aren't that clear cut. E.g. in Linux (quite monolithic) you'll find FUSE (Filesystems in USErspace). In Unix (monolithic) the graphics system is X, and that one (while userspace) is (or was) granted direct access to interrupts and I/O under Linux at least. It is quite common to have IPC in userspace, while in Windows (was once a microkernel, now a strange hybrid) it is completely part of the sort-of microkernel.

Just for laughs, a while back the "monolithic" Linux kernel was smaller than the Mach "microkernel" alone...


Proving a language is not context free using the Pumping Lemma To prove that $L=\{0^m1^n|n \text{ divides } m,\text{ } m,n\gt0\}$ is not a CFG, I applied the pumping lemma. I chose $w=0^{21p}1^{7p}$ for the pumping constant p. By the pumping lemma, $w=xyuvz, |yuv|\leq p, |w|\geq p, |yv|>0, xy^iuv^iz \in L \forall i>0$

Take $i=0$ then consider 3 cases:

Case 1:$yuv$ is only a substring of $0s$.

Then $w'=0^a1^{7p} \text{ with } 21p>a\geq 20p$. In this case, $a$ is not divided by $7p$

Case 2:$yuv$ is only a substring of $1s$.

Then $w'=0^{21p}1^{b} \text{ with } 7p>b\geq 6p$. In this case, $21p$ is not divided by $b$

Case 3:$yuv$ contains both $0s$ and $1s$.

Now I am quite sure this also works when $yuv$ includes both $1s$ and $0s$.
We get $w'=0^{21p-a}1^{7p-b} \text{ with }p>a>0, p>b>0 \text{ and } p\geq a+b$.

I just can't figure out how to formally state how a contradiction arises from case 3. How can I prove that case 3 also fails? Thanks!

You can try to take a different value for $i$ in that case. It is not necessary to fix one $i$, but the $i$ chosen may depend on the chosen partition $xyuvz$. Will $7p+ib$ always divide $21p+ia$?


Calculating modulus of large non-factored numbers The internet is full of algorithms to calculate the modulo operation of large numbers that have the form $a^e \bmod p$. How about numbers with unknown factorization. More precisely, let's say I have a 4-byte sized modulus prime $p$, and a large number $a$ stored in memory as an array of bytes, that is, $a = [a_{k-1}, a_{k-2},\dots, a_0]$, where $ k \gg 4$.

How to calculate the modulo operation $a \bmod p$ efficiently?
Please, cite a reference for your algorithm if it is possible.

The map from natural numbers to the ring of remainders is a homomorphism, which is a way to say that it has all sorts of nice properties with respect to operations + and *. In particular, a+b has the same remainder as mod_p(a) + mod_p(b) and a*b, the same as mod_p(a)*mod_p(b).

So, mod_p(a_0 + a_1*2^8 + a_2*2^16 + ...) = mod_p(mod_p(a_0) + mod_p(a_1)*mod_p(2^8) + mod_p(a_2)*mod_p(2^16) + ...).


Augmenting paths of two matchings Given a graph $G(V, E)$ and two matchings $M \subset E$ and $M' \subseteq E$ with $|M'| > |M|$, how can one prove that  $M\oplus M'$ ($\oplus$ denotes the symmetric difference) must contain at least $|M'|-|M|$ augmenting paths of $M$? I know that there have to exist some $M$-augmenting paths since $M$ is not a maximum matching, but I don't really know how to prove the above.

Proof: We first notice a few things about the graph $G(V(M' \oplus M), M'\oplus M)$:

If there exists a cycle in $G$, it will be of even length. One can easily see this because if it was of odd length, two edges of the same matching would have to be incident to the same vertex which contradicts the definition of a matching. Hence, cycles don't contribute to the difference in edges (remember, $|M'| > |M|$)
There can be paths of even and odd length. The former are not of any interest since they contain the same amount of edges from both matchings, not contributing to the difference. On the other hand, paths of odd length that are $M$-augmenting contain exactly one more edges of $M'$ than of $M$. This is because the paths edges alternate between edges of $M'$ and $M$ (also for the even paths) since no two edges of the same matching can constitute a path (as they don't share common vertices). Moreover, a paths of odd length that is $M'$ augmenting isn't of much interest since it doesn't contribute to the difference in edges.

From (2.) follows that only the $M$-augmenting paths of odd length contribute to the difference $|M'| - |M| > 0$ (those paths can also be of length 1). Since each of those paths extends the matching $M$ by one edge, there must at least exist $|M'| - |M|$ of those $M$-augmenting paths since $|M| + |M'| - |M| = |M'|$. Notice that there can be more than $|M'| - |M|$ augmenting paths of $M$ if $M'$ is not a maximum matching (why?).


Maximizing book picked using two stacks There are two stacks $S_1$ and $S_2$ of books. Each book in stack has a weight. You are given a net weight $W$ of books that can be picked. You have to maximize the number of books that can be picked. Note that each time you can either pick from $S_1$ or $S_2$ only.

eg: $S_1 = \langle 5, 1, 1\rangle$,
$S_2 = \langle 1,2,6 \rangle$, $W=10$.

So the answer is $5$ (pick $1$ and $2$ from $S_2$, then all elements from $S_1$)

I know this question can be done with a greedy approach by comparing top elements of both stacks, but can we solve it with the concept of trees?

Is there any other data structure that can be used to solve this problem?

The greedy algorithm does not always work. Example: $S_1 = \langle 3, 1, 1,1\rangle$, $S_2 = \langle 2, 2,2\rangle$, $W=6$.

In general, let $S_1 = \langle x_1, \dots, x_k \rangle$ and $S_2 = \langle y_1, \dots, y_h \rangle$. I will assume that individual book weights are positive integers.
To solve your problem optimally you can use a sliding-window approach. Compute, for each $i=0,\dots k$, the quantity $X_i
= \sum_{j=1}^i x_i$. Similarly, for each $i=0,\dots,h$ compute $Y_i
= \sum_{j=1}^i y_i$.

Now start with $i=0$ and $j=h$ and iteratively do the following:

If $X_i + Y_j \le W$ consider the solution $(i,j)$ that selects $i$ elements from $S_1$ and $j$ elements from $S_2$ as a candidate solution.
If $i=k$ and $j=0$ stop and return the solution that maximizes $i'+j'$ among all candidate solutions $(i',j')$.
If $X_i + Y_j \le W$ and $i<k$, or if $j=0$, increment $i$ by $1$.
Otherwise, decrement $j$ by $1$.

To see that this algorithm must work consider an optimal solution that selects $i^*$ books from $S_1$ and $j^*$ books from $S_2$. Since, at the end of the algorithm, $i=k$ and $j=0$ there must be some iteration for which $i=i^*$ or $j=j^*$. Consider the first such iteration.

If $i=i^*$ then $j \ge j^*$ meaning that for all $j' = j^*+1, \dots, j$ we must have $X_i + Y_{j'} > W$. This shows that in the next $j-j^*$ iterations $j$ will be decremented until it reaches $j^*$.

If $j= j^*$ then $i \le i^*$ meaning that for all $i' = i, \dots, i^*-1$ we must have $X_{i'} + Y_j > W$. This shows that in the next $i^*-i$ iterations $i$ will be incremented until it reaches $i^*$.

In any case the pair $i=i^*$ and $j=j^*$ is considered by one iteration of the algorithm and, since $X_{i^*} + Y_{j^*} \le W$ the solution  $(i^*,j^*)$ must be one of the candidate solutions.

A straightforward implementation requires linear time in the combined size $n$ of the two stacks.

Since you can actually stop computing $X_i$ (resp. $Y_i$) as soon as $X_i \ge M$ (resp. $Y_i \ge M$) you can reduce the time complexity to $O(\min\{n, W\})$.


Landau Notation, Definitions: Limits vs. Corman's When dealing with Landau notation, $\Theta, O,\Omega,o,\omega$, why do some texts choose the Corman style definitions, i.e.:

$$o(g(n))=\{ f(n): \forall c>0:\exists n_0>0:\; 0\leq f(n) < cg(n): \; \forall n\geq n_0 \}$$

and some texts use limit based definitions such as:

$$\lim_{n\to\infty}\frac{f(n)}{g(n)}=0\Rightarrow f(n)\in o(g(n))$$

Is there any inherent advantage to one definition or the other?  Or is it more a matter of the author's personal preference?

To expand on Raphael's answer, both definitions are equivalent. The second definition is Landau-style (i.e. number theory style), while the first definition is computer science style.

The Landau-style definition is clearly more succinct and I personally prefer it. There are two reasons to state the definition in the computer science style:

Textbook writers don't want to assume that their readers know calculus.
The Landau-style definition for $f = \Theta(g)$ is more awkward: $\lim\inf f/g > 0$, $\lim\sup f/g < \infty$.


Probabilistic poly-time machine always halts on all inputs? In the usual definition of probabilistic poly-time machine it is said that the machine halts in polynomial time for all inputs.

Is the intention really to say that the machine halts for all inputs, or that if it halts it must be in polynomial time?

We say that a probabilistic Turing machine M runs in time T(n) if for any input x M halts in less than T(|x|) steps independently of the random choices it makes during the computation (worst case over all possible computation paths).

For example, the most general definition of Probabilistic Polynomial-time, namely  PP, is:

  A language L is in PP if and only if there exists a probabilistic Turing machine M, such that

  M runs for polynomial time on all inputs
  For all x in L, M outputs 1 with probability strictly greater than 1/2
  For all x not in L, M outputs 1 with probability less than or equal to 1/2.

It always halts in polynomial time on all inputs.

Because the two probabilities can be made very close ($\frac{1}{2}+\frac{1}{2^n},\frac{1}{2}-\frac{1}{2^n}$), it would take potentially an exponential number of runs to distinguish accepting from rejecting with good confidence; so a more representative and efficient probabilistic class is BPP (Bounded-error Probabilistic Polynomial-time):

  A language L is in BPP if and only if there exists a probabilistic Turing machine M, such that

  M runs for polynomial time on all inputs
  For all x in L, M outputs 1 with probability greater than or equal to 2/3
  For all x not in L, M outputs 1 with probability less than or equal to 1/3.

Again, M always halts in polynomial time on all inputs.

See also the complexity class RP (Randomized Polynomial time).

We have: $RP \subseteq BPP \subseteq PP$


Ambiguous grammar to equivalent unambiguous grammar I stumbled on this ambiguous grammar and I've been trying to make it unambiguous but it's still ambiguous.

Given the ambiguous CFG :
$S \to A\mid B$
$A \to aAb\mid ab$
$B \to abB\mid \epsilon$

My closet try was:

Given the ambiguous CFG :
$S \to A$
$A \to aAb\mid C$
$B \to b$
$C \to abC\mid\epsilon$

But the string "$ab$" is ambiguous

As you have observed, the only problem in the original CFG is that the string $ab$ can be generated by both $A$ and $B$.

Here is a hint. Instead of generating $ab, a^2b^2, a^3b^3,\cdots$, can you let $A$ generate $a^2b^2, a^3b^3,\cdots$ without generating $ab$?


MAP estimation (for stationary iid gaussian environment) This is my first post, and have been self studying Haykin's Neural Networks and Learning Machines book.  I'm not sure if this is a typo or if I'm doing something wrong, but I've been stuck on a statement on page 75.

The context was the process of finding a Maximum likelihood estimate for a parameter vector assuming a stationary, iid, and Gaussian environment.

Given:
d is a scalar, i indexes time from 1 to N, and $\mathbf{w},\mathbf{x}_i $ are  m-dimensional vectors.

$\hat{w}_{MAP} = max_{\mathbf{w}}[-\frac{1}{2}\Sigma_{i=1}^{N}(d_i - \mathbf{w}^T\mathbf{x}_i)^2 - \frac{\lambda}{2}||\mathbf{w}||^2]$

we should get the same result if instead we find the minimum of the quadratic function

$E(\mathbf{x}) = \frac{1}{2}\Sigma_{i=1}^{N}(d_i - \mathbf{w}^T\mathbf{x}_i)^2 + \frac{\lambda}{2}||\mathbf{w}||^2$

Haykin says you should arrive at the result (by differentiation wrt $\mathbf{w}$ and setting the result to 0)

$\hat{w}_{MAP} = (R_{xx} + \lambda I)^{-1} r_{dx}$

where $R_{xx} = -\Sigma_{i=1}^N \Sigma_{j=1}^N \mathbf{x}_i \mathbf{x}_j^T $ is the M*M correlation matrix of x and $r_{dx} = -\Sigma_{j=1}^N \mathbf{x}_i d_i$

My question is why isn't $R_{xx} = -\Sigma_{i=1}^N \mathbf{x}_i \mathbf{x}_i^T?$
Haykin goes through about a paragraph saying how the correlation matrix is time averaged and I think this is an important point.
Thanks for any help!

$\newcommand{\bd}{\mathbf{d}}\newcommand{\bw}{\mathbf{w}}\newcommand{\bX}{\mathbf{X}}$Your observation is correct--it appears to be several typos. To see why let's re-write the likelihood equation to something a bit more suitable for differentiating using matrix/vector notation. $$\text{NLL}(w) = \frac{1}{2}||\bd - \bX\bw||^2_2 + \frac{\lambda}{2}||\bw||^2_2,$$

where $\bX$ is our matrix of observations, $\bd$ is our vector of labels and $\bw$ is our vector parameter of interest. Taking the derivative yields,
$$\frac{\partial \text{NLL}}{\partial \bw} = -\bX^t(\bd - \bX\bw) + \lambda\bw.$$

Setting this equal to 0 and solving gives,
$$ \begin{align*}\lambda \bw &= \bX^t(\bd - \bX\bw) \\
&= \bX^t\bd - \bX^t\bX\bw \iff\\
\lambda\bw + \bX^t\bX\bw &= \bX^t\bd \iff \\
(\lambda\mathbf{I} + \bX^t\bX)\bw &= \bX^t\bd \iff \\
\hat{\bw}_{\text{MAP}} &= (\lambda\mathbf{I} + \bX^t\bX)^{-1}(\bX^t\bd).
\end{align*}$$

Notice that $$\bX^t\bX = \sum_i \mathbf{x_i} \mathbf{x_i}^t = R_{xx}$$ and $$\bX^t\bd = \sum_i \mathbf{x_i} d_i = r_{dx}.$$


Finding the number of iterations to a recurrence I have an algorithm where the number of items in my set decrease by $\sigma/(1+\sigma)$ on each iteration until all items are exhausted.

$$
\begin{align*}
S_0 &= S \\
S_{k+1} &= S_k - S_k \frac{\sigma}{1+\sigma}
\end{align*}
$$

Here $\sigma$ is a small value.

How can I find number of iterations? I know it is a geometric series but can't seem to simplify for number of iterations.

Presumably the correct form of the recursive step is
$$ S_{k+1} \leq S_k - S_k \frac{\sigma}{1+\sigma} = \frac{S_k}{1+\sigma}. $$
Using induction, we can show that
$$ S_t \leq \frac{S}{(1+\sigma)^t}. $$
So the algorithm will end by the time $T$ satisfying
$$ \frac{S}{(1+\sigma)^T} < 1.$$
I'll let you solve this yourself.


Requirements for emulation What are the complete specifications that must be documented in order to ensure the correct execution of a particular program written in Java? For instance, if one were archiving a program for long-term preservation, and no testing or porting would be done.

I need to be able to compile and execute the Java program. Thus preserving the byte code or capturing the whole thing as a VMware image are excluded. The JVM could be saved as a VMware image though, and compiled libraries that are linked to the compiled code are OK, too. However, if there are dependencies on the OS, the architecture of the machine executing the JVM, the networking environment, external libraries, specification of the Java version used, etc. etc. these must all be listed. Some tech leaders in Dig Pres claim that any program written in Java will be executable "forever". How to do it?

Hoeven et al. studied the problem of digital preservation through emulation:

... Digital preservation does not end with the careful storage of digital objects. In order
to keep these objects accessible, a continuous effort towards the development of
strategies for permanent access is required ....

They ended up with a modular emulation model and the need of an Universal Virtual Machine (UVM):

... The basis of the modular emulation model is founded on the Universal Virtual
Machine (UVM). The UVM is a platform- and time-independent layer on top of the
underlying future host platform. As a result, programs that are developed for the
UVM will continue to work even if the host platform changes. It not only consists of a general purpose processor and memory, but also offers additional functionality for input and output (I/O) communication with peripheral devices (like keyboard, storage, graphics,
networking) between host and target platform. This will be provided by the interface
layer.

.. and started the "Dioscuri project": a modular emulator for digital preservation. Not surprisingly, they chose Java to implement it:

... Java has been chosen as programming language. The main reason is its possibility to run Java code on a large variety of computer platforms using the Java Virtual Machine (JVM) without the need to recompile the source code. Recompilation is a risk factor since program code is adapted to a specific underlying computer platform. Although today’s compilers are very advanced, it can still result in different functionality of the same emulator compiled for different platforms. By avoiding this step, the emulator will be more stable and portable. Using the JVM instead provides similar results to the use of a UVM as discussed above....

The papers:

"Modular emulation as a long-term preservation strategy for digital objects" (2005)
"Emulation for Digital Preservation in Practice: The Results" (2007)

EDIT: the last changelog  of the Dioscuri project is dated: 19-Jan-2011
... so - perhaps - a new project/research should be started: "How to preserve the digital preservation tools?" :-D :-D

EDIT 2: just my personal opinion: if the Java program does useful things, humanity will preserve it without the need of any efforts by its author :-)


What is the running time of this recursive algorithm? I made the following (ungolfed) Haskell program for the code golf challenge of computing the first $n$ values of A229037.

This is my proposed solution to compute the $n$th value:

a n | n<1        = 0
    | n<3        = 1
    | otherwise  = head (goods n)

goods n = [x | x <- [1..], isGood x n]

isGood x n = and [ x - a(n-k) /= a(n-k) - a(n-k-k) || a(n-k-k) == 0 | k <- [1..n] ]

Note that Haskell does not automatically cache or memoize these values.

The OEIS page for the sequence gives the fact that $a(n) \leq (n+1)/2$, so the [1..] could be replaced by [1..(n+1)/2], as the algorithm will never reach an $x$ greater than $\frac{n+1}{2}$.

Attempting to count function calls, I derived the following upper bound $T(n)$, the number of function calls that the algorithm takes for an input $n$:

$$ \begin{align}
 T(n) &= \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} 2~T(n-k) + 2~T(n-2 k) \\
&\leq \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} ~T(n-k)\\
&\leq \sum_{x=1}^{(n+1)/{2}} \sum_{k=1}^{n} 4~T(n-1)\\
&\leq \sum_{x=1}^{(n+1)/{2}} 4~n~T(n-1)\\
&\leq 4~n~T(n-1)~\frac{n+1}{2}\\
&\leq 2~n~(n+1)~T(n-1) )
\end{align}$$

I plugged the final formula into Mathematica:

RSolve[{T[n] == 2*T[n - 1]*n*(n + 1), T[1] == 1}, T[n], n]

And got, after a little simplification: $T(n) \leq ~2^n~n!~(n + 1)!$

The average ratio between this and the Haskell program execution time, for $n \in [12,20]$ is  $2.0 \cdot 10^{39}$ and the standard deviation of the ratios is around $6.0 \cdot 10^{39}$. (Curiously enough, the log plot of the ratios appears to be a straight line).

The ratios with the first line, defining $T(n)$, have a mean and standard deviation of $4.8 \cdot 10^6$ and $1.8 \cdot 10^6$, respectively, but its plot jumps around a lot.

How can I get a better bound on the time complexity of this algorithm?

Here is the algorithm in valid C (minus forward declarations), which I believe is roughly equivalent to the Haskell code:

int a(int n){
    if (n < 1) {
        return 0;
    } else if (n < 3) {
        return 1;
    } else {
        return lowestValid(n);
    }
}

int lowestValid(int n){
    int possible = 1; // Without checking, we know that this will not exceed (n+1)/2

    while (notGood(possible, n)) {
        possible++;
    }
    return possible;
}

int notGood(int possible, int n){
    int k = 1;

    while (k <= n) {
        if ( ((possible - a(n-k)) == (a(n-k) - a(n-2*k))) && (a(n-2*k) != 0) ) {
            return 1;
        } else {
            k++;
        }
    }
    return 0;
}

The C version takes about 5 minutes to compute $a(17)$ and the Haskell version takes about the same for $a(19)$.

The first times of the versions:

Haskell: [0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,0.0,1.0e-2,3.0e-2,9.0e-2,0.34,1.42,11.77,71.68,184.37,1815.91]
C:       [2.0e-6, 1.0e-6, 1.0e-6, 2.0e-6, 1.0e-6, 6.0e-6, 0.00003,0.00027, 0.002209, 0.005127, 0.016665, 0.080549, 0.243611, 0.821537, 4.56265, 24.2044, 272.212]

You can write your recurrence as
$$
T(n) = (n+1)(T(n-1) + 2T(n-2) + T(n-3) + 2T(n-4) + \cdots).
$$
In particular, $T(n) \geq (n+1) T(n-1)$. This means that the sequence $T(n)$ grows very rapidly, and in particular
$$
T(n-1) + 2T(n-2) + \cdots \leq T(n-1) \left[ 1 + \frac{2}{n} + \frac{1}{n(n-1)} + \frac{2}{n(n-1)(n-2)} + \cdots \right] = (1+O(1/n)) T(n-1).
$$
Therefore
$$
T(n) \leq (n+O(1)) T(n-1).
$$
This means that
$$
T(n) = O((n+O(1))!),
$$
and so
$$
T(n) = O\left(n^{O(1)} (n/e)^n\right).
$$
This improves on your bound by a square root.


minimum travel from point to point with incremental steps It's my first time to make a question here.
I have a curious problem about algorithm, in the center of Cartesian plane (0,0) I need to go to another point (x,y) -x and y are belong to Z numbers - but I only can use horizontaly and verticaly steps and this steps increases one by one units, a unit is a distance from (0,0) to (0,1), (1,0), (-1,0) or (0,-1).
For example, I need to go to (1,1) point and steps are:

Go to (1,0), a step of 1 unit.
Go to (1,-2) a step of 2 units.
Finally, go to (1,1) a step of 3 units.

And for this example the answer is I need 3 steps with 6 units of distance.
Obviously, there are several ways to go to a point from center but
the problem needs the minimal.
Are there a formula or an algorithm to find the minimum count of steps and the distance of this way?
Well, if you find one of them (steps or distance), the other one is easy to find because the distance is a sum of N (count of steps) first natural numbers.
Thanks for read this and for your answers and suggestions.

Interesting question. It is surprising that the answer depends only on $|x|+|y|$. For example, the same number of the steps is needed to reach $(1,1)$ or $(0,2)$.

The minimum step is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is even and nonnegative.
Here is an $O(1)$-time algorithm that returns the value described above, where least_n, i.e., $\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$, is the least nonnegative integer $n$ such that $n(n+1)/2-(|x|+|y|)\ge0$.
def minimum_steps(x,y):
    distance_to_origin := absolute_value(x) + absolute_value(y)
    least_n := ceiling((-1 + square_root(8 * distance_to_origin + 1)) / 2)
    gap := n * (n + 1) / 2 - distance_to_origin
    # 0 <= gap <= n - 1

    if gap is even:
        return least_n
    else if n is even:
        return least_n + 1
    else:
        return least_n + 2

Given the number of steps $s$, the distance travelled is $1+2+\cdots+s=s(s+1)/2$.

The correctness of the formula and algorithm above comes from the following characterization.
Proposition. The minimum count of steps from $(0,0)$ to $(x,y)$ is the least non-negative integer $n$ such that $n(n+1)/2-(|x|+|y|)$ is nonnegative and even.
Proof. If we can go to $(x,y)$ in $n$ steps, the sum of some numbers between 1 and $n$ or their negations must be $x$ and the sum of the remaining numbers or their negations must be $y$, i.e.,
$$\pm1\pm2\pm\cdots\pm n = |x| + |y|$$
for some choice of all $\pm$'s. That means,
$$1+2+\cdots+ n - (|x| + |y|)$$
is nonnegative and even.
Now it is enough to prove that $(x,y)$ is reachable in $n$ steps if $n(n+1)/2-(|x|+|y|)$ is nonnegative and even. Let us prove it by induction on $n$.

The base cases, $n=0$ or $1$ means $(x,y)=(0,0), (0,1), (1,0)$. These cases are immediate to verify.
Suppose, as induction hypothesis, it is correct for smaller $n$'s. Now consider the case of $n\ge2$ with $n(n+1)/2-(|x|+|y|)$ nonnegative and even. We can assume $x$ and $y$ are non-negative; otherwise, for example, if $x$ is negative, we can change $x$ to its absolute value and reverse the direction of all steps that are parallel to $X$-axis.
There are three cases.

$x \ge n$.  Let $x'= x-n$. Then $$(n-1)n/2-(|x'|+|y|)=n(n+1)/2-(|x|+|y|)$$ is nonnegative and even. By induction hypothesis, we can go to $(x',y)$ in $n-1$ steps. To reach $(x,y)$ in $n$ steps, we continue $n$ units in X-direction.
$y\ge n$. This is symmetric to the case above.
$0\le x\lt n$ and $0\le y\lt n$. There are two subcases.

$x\ge 2$ and $y\ge 2$. Let $x'=(n-1)-x$ and $y'=n-y$. Then $|x'|\le n-3$ and $|y'|\le n-2$. $$(n-2)(n-1)/2-(|x'|+|y'|)\ge(n-3)(n-4)/2\ge0.$$ The parity of $(n-1)(n-1)/2-(|x'|+|y'|)$ is the same as $n(n+1)/2-(|x|+|y|)$, i.e, even. By induction hypothesis, we can go to $(x',y')$ in $n-2$ steps . Reversing all the steps, we can go to $(-x', -y')$ in $n-2$ steps as well. To reach $(x,y)$ in $n$ steps, we can continue with two more steps, $n$ units in X-direction and $n+1$ units in Y-direction.
One of $x$ and $y$ is $0$ or $1$. Let $g(k)=k(k+1)/2-(|x|+|y|)$. The smallest nonnegative integer such that $g(k)\ge0$ is  $m=\left\lceil\frac{-1+\sqrt{8(|x|+|y|)+1}}2\right\rceil$. Since both $x$ and $y$ are $\lt n$ and one of them is $0$ or $1$, $$m\le \frac{1+\sqrt{8n+1}}2.$$
When $g(m)$ is even, $n=m$ by definition. When $g$ is odd, since either $g(m+1)=g(m)+(m+1)$ or $g(m+2)=g(m)+(m+1)+(m+2)$ must be even,  either $m+1$ or $m+2$ must be $n$. So, whether $g(m)$ is even or odd, we have $$n\le m+2.$$
Combing the two inequalities above, we have
$$n\le \frac{5+\sqrt{8n+1}}2,$$
which implies $n\le 6$.  Since X-direction and Y-direction are symmetric, let us assume $y=0,1$. Since $x\lt n$, $x\lt 6$. So it is enough to verify the cases where $(x,y)$ $\in $ $\{(0,0),(0,1),$ $(1,0),(1,1),$ $(2,0), (2,1),$ $(3,0), (3,1),$ $(4,0), (4,1),$ $(5,0), (5,1)\}.$ It is easy to verify each of them.

$\ \checkmark$


Operation of the Ford–Fulkerson algorithm given an almost maximum flow I have been assigned the question:

Let $G$ be a flow network and $f^*$ be the maximum flow computed by the Ford-Fulkerson algorithm. Consider a new flow network $G'$ constructed by increasing the capacity of exactly one of $G$'s edges by one.
Using the maximum-flow and minimum-cut theorem, argue that if we run the Ford-Fulkerson algorithm on $G'$ with $f^*$ as the initial flow, the while-loop shall terminate in at most one iteration.

But I feel like the loop can run more than once...
Considering a base case where $G$ has one edge between the sink and source with a capacity of 1.
Then $G'$ will have one edge with a capacity of 2.
So then when we run the Ford–Fulkerson algorithm with an initial flow of $f^* = 1$, the first loop will leave a residual graph with an edge with a capacity of 1, and therefore the loop will run for a second time.

You are interpreting the question too literally. The question claims that only one augmentation step will be performed. In your example, we augment $f^*$ by pushing one more unit of flow, and then we reach the maximum flow of the updated network.


Is there an algorithm to achieve optimal compression in a "streamed" manner, assuming equal probability of each possibility? (Sorry for the question title; edits are welcome.)

Let's say that you have a set of data made of repeating units, consisting of a value with $2$ possibilities, a value with $3$ possibilities, $5$ possibilities, $4$ possibilities, repeat. The total number of possibilities per unit is $2\times3\times5\times4=120\text{ possibilities}$. Assuming that these are all equally probable, that's $\log_2120\approx6.9\text{ bits}$. This means that the minimum space required to represent $1$ unit is $1\text{ Byte}$, but the minimum space required to represent $1000$ units is $864\text{B}$.

The naïve way of producing this compression would be to put them all into a base-120 number, then convert this to binary. However, this requires having access to all of the data at once in order to decompress it. There must[citation needed] be some algorithm that can take in a stream of compressed data, output a stream of decompressed data, and only use finite memory, but I can't find one.

Please describe and explain such an algorithm, if one exists.

However, this requires having access to all of the data at once in order to decompress it.

Not true. The trick is to compress backwards, from the last symbol, to the first. You do need all the data at once to compress though.

However, what you are looking for can be done with arithmetic coding, without even needing access to all of the data at once during compression.


Proving that a problem is in NP I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The problem $D$ is a decision problem)

Edit: Changed $P$ to $D$

The two requirements for a problem to be in NP are

it must be possible to check a given solution in polynomial time;
there must be some polynomial $f$ such that solutions to instances of length $n$ have size at most $f(n)$.

Properly, the "solutions" are referred to as "certificates" since they don't have to be an actual solution to the problem. Normally, the certificate to something like a satisfiability problem would be a satisfying truth assignment, but anything that "proves" the instance is in the langauge is acceptable. In particular, the proof that every language in NP can be thought of in these terms uses a description of the accepting computation of a Turing machine as the certificate.

This gives intuition why the certificate has to have polynomial length: the Turing machine was only allowed to run for a polynomial number of steps. Indeed, if you dropped the polynomial length requirement on the certificate, even the halting problem would "be in NP". The certificate would be a description of the steps taken by the Turing machine before it halts; you can easily check in polynomial time that a certificate is valid, but the certificate itself might have arbitrary length.


Easiest way to write a grammar? When I see a problem like "Write a grammar for a language $L$ if $L = \{..\}$" for me is a matter of "instinct" the way that one can define productions. For example given the following exercise:

  Let $L$ a language which alphabet is $\{x,y,z\}$ and accepts strings
  $w$ where there aren't consecutive $x$'s nor consecutive $y$'s nor
  consecutive $z$'s.

My first aproaching was to stablish that $x$, $y$ and $z$ each one are in $L$, that is:

$$S \rightarrow x \mid y \mid z$$

If the string has an $x$, there can be a consecutive $y$ or $z$, similarly for the other symbols. I assume that there are productions $A$, $B$ and $C$ that make the work, so the start production is:

$$S \rightarrow xA\mid yB\mid zC\mid x\mid y\mid z$$

Therefore $S$ can be splitted to define $A$, $B$ and $C$:

$\begin{eqnarray*}S &\rightarrow& A \mid  B \mid  C \\A &\rightarrow&  yB \mid  zC \mid  y \mid  z \\ B &\rightarrow&  xA \mid  zC \mid  x \mid  z\\ C &\rightarrow&  xA \mid  yB \mid  x \mid  y \end{eqnarray*}$

But as you all can see this is just my version, I started with base strings accepted by $L$ and then I followed my own thought of how to build the grammar. Is there a easy way to do this? or some advice for similar languages? (like those which have different number of symbols).

Of course "instinct"always helps, but writing a grammar is more or less writing a program, but with limited resources.

Your example matches a regular language. Those languages can be defined using right-linear grammars but I prefer finite state automata. Programming linear grammars (and finite state automata) requires thinking in states. What is the characteristic information about the string I have seen so far.

In your example the "state" consists of the last letter read. OK, since your task is to avoid reading a letter twice. In other examples you might want to do some counting ("if the string contains exactly four $a$'s it ends in $b$") or modulo counting ("the number of $a$'s is even"). Perhaps you want to do a kind of pattern recognition ("words that do not contain $00110$") and you keep track of the part of the pattern you have just seen.

Sometimes the requirements consist of a Boolean combination of properties. Then you keep track of both of them in the state and react on what you know.

You see: just like programming.

If the grammar is more complicated, like context-free you probably want to think in terms of trees. That is the structure they use to derive strings.


Is there a 'string stack' data structure that supports these string operations? I'm looking for a data structure that stores a set of strings over a character set $\Sigma$, capable of performing the following operations. We denote $\mathcal{D}(S)$ as the data structure storing the set of strings $S$.

Add-Prefix-Set on $\mathcal{D}(S)$: given some set $T$ of (possibly empty) strings, whose size is bounded by a constant and whose string lengths are bounded by a constant, return $\mathcal{D}( \{ t s\ |\ t \in T, s \in S\} )$. Both these bounding constants are global: they are the same for all inputs $T$.
Get-Prefixes on $\mathcal{D}(S)$: return $\{ a \ | \ as \in S, a \in \Sigma \}$. Note that I don't really mind what structure is used for this set, as long as I can enumerate its contents in $O(|\Sigma|)$ time.
Remove-Prefixes on $\mathcal{D}(S)$: return $\mathcal{D}( \{ s \ | \ as \in S, a \in \Sigma  \} )$.
Merge: given $\mathcal{D}(S)$ and $\mathcal{D}(T)$, return $\mathcal{D}(S \cup T)$.

Now, I'd really like to do all these operations in $O(1)$ time, but I'm fine with a structure that does all these operations in $o(n)$ time, where $n$ is the length of the longest string in the structure. In the case of the merge, I'd like a $o(n_1+n_2)$ running time, where $n_1$ is $n$ for the first and $n_2$ the $n$ for the second structure.

An additional requirement is that the structure is immutable, or at least that the above operations return 'new' structures such that pointers to the old ones still function as before.

A note about amortization: that is fine, but you have to watch out for persistence. As I re-use old structures all the time, I'll be in trouble if I hit a worst case with some particular set of operations on the same structure (so ignoring the new structures it creates).

I'd like to use such a structure in a parsing algorithm I'm working on; the above structure would hold the lookahead I need for the algorithm.

I've already considered using a trie, but the main problem is that I don't know how to merge tries efficiently. If the set of strings for Add-Prefix-Set consists of only single-character strings, then you could store these sets in a stack, which would give you $O(1)$ running times for the first three operations. However, this approach doesn't work for merging either.

Finally, note that I'm not interested in factors $|\Sigma|$: this is constant for all I care.

I thought for quite some time, but didn't find the problem with doing all of your operations in the most stupid possible way in a trie-like DAG structure:
Add-Prefix-Set
Create a trie of strings from $T$. Connect each leaf node to the root of the old trie.
Complexity: $O(|T|)$
Merge
Unite roots of two structures: make all children nodes of the second root children of the first node. You may now have multiple edges marked with the same character going from the same node.
Complexity: $O(1)$
Lazy update of the root

For each character unite all children of the root accessible by the edges marked with this character. ($O(|\Sigma|)$ + Amortized $O(1)$ for each edge ever added)
Delete all edges going into the root from the top. (Can happen after Remove-prefixes, amortized $O(1)$ for each edge ever added)

Get-prefixes
Lazy update the root. Now find all children of the root and report set of letters on edges going to them.
Complexity: $O(|\Sigma|)$
Remove-prefixes
Lazy update the root. Unite all children of the root and set the root pointer to the result of this unite. Lazy update the new root.
Complexity: $O(|\Sigma|)$ + Lazy update
Persistence
All information about this data structure can be saved in arrays, with $O(1)$ information per node plus $O(|\Sigma|)$ information for each child of the node. Each operation can be held out as set of assignments in these arrays. Use persistent range tree or any other data structure that can be viewed as a persistent array. Additional multiplier for memory and space complexity $O(log N)$, where $N$ is the total number of characters in all queries.


Is solving a quadratic equation using Turing machine impossible? I've just started Algorithms at university. There's a task to write an algorithm for a Turing machine to solve quadratic equations. The task doesn't specify if it's x^2+bx+c or ax^2+bx+c. I've searched whole bunch of information over Russian and English Internet.

I did find articles, which say it's not possible because we've got real numbers A, B, C. Please confirm if that's true. I may not get it correct.. But I think that's impossible. I still don't know how to prove my thoughts.

Thanks in advance!

The problem is not clear enough. Turing Machines can or cannot solve problems if those problems are languages, that means, sets of strings over a finite alphabet. You cannot represent all reals in this way, so it is not even a problem that a TM could even attempt to solve. In the same fashion that world hunger is not a problem in the precise sense that a computational complexity requires it to be.

The problem is obviously solvable if you define it as the sets of words that encode three rational numbers a, b and c in a standard way.  How do you solve this? Well, the construction of the machine that does this is rather complicated, but you know how to do this in let's say, Python, right? So you can always compile your Python code into a TM.


Turing Completeness of System Which Randomly Fails to Complete Calculations If one were to create a variant of a turing complete language which upon completing a calculation randomly changes the answer by one, would it be Turing complete? For example, say I had a Python implementation which, upon every variable assignment, with probability $\frac13$ decreased the value by $1$, with probability $\frac13$ increased the value by $1$ and otherwise kept the value constant, would it be Turing complete? This seems to be able to perform all of the calculations which Python is able to perform, just not reliably.

I've gone around and around on this one.  It would seem that we've landed on "No, it would not be Turing Complete, although we might be able to approximate it with a bounded probability of error on either accuracy or returning in finite time."

In your post, you said "just not reliably"... that is, in fact, a crucial part of the definition.  To be Turing-complete, we have to be able to exactly simulate a single taped Turing machine -- getting it right "sometimes" isn't any better than flipping a coin to determine if it's raining outside with "50% accuracy".

In the given example, you seem to suggest that the random failures only occur on assignment, not for other operations in the computer.  Does this affect assignments performed by the programmer alone, or internal assignments performed as intermediate steps by the compiler?  If it only affects assignments performed by the programmer, many programs could be written (in horrendously terrifying complexity and near impossible to debug) without creating and assigning any variables at all.  In this case, I suppose it would be similar to a Turing tarpit.

If the programmer HAD to assign variables, they should be able to use something in the vein of the old Heinlein "Tell me 3 times", assigning the variable in an array repeatedly (say 100 times, or until 3 distinct values have been saved) and then use the median value (since all values are x, x-1, or x+1, the median value, not median result, must be the correct one).  This would cut into performance HORRIBLY, but should, typically, arrive at correct values.  (In fairness to @DavidRicherby, I concede that we cannot ensure both that we arrive at an answer and that it is correct with 100% certainty; for a look at how we could arrive at 3 distinct values without additional assignments, consider the following approach:

# function sum : x,y $\rightarrow$ z
var a = x + y;   // first assignment, may be x, x-1, or x+1
var b = x + y;
while (a == b)
  b = x + y;     // if this loop finishes, b is now distinct from a
var c = x + y;
while ((a == c) || (b == c))
  c = x + y;     // if this loop finishes, c is now distinct from a and b
if ((a < b) && (b < c))
  return b;
if ((b < a) && (a < c))
  return a;
// repeat for the other combinations; there should be 6 total if statements.

)

If the compiler can introduce intermediate assignment operations that the programmer did not that also suffer from this drawback (say, at the end of every elementary computation), or if there are other operations affected by this glitch (the killer one in my above example being the comparison operators), then we cannot simulate a Turing-complete language (or machine) at any speed -- we will only be right 1 out of every $3^n$ times on average, where $n$ is the number of operations we can't correct for.

The Short Version of My Answer:

I can try to check for errors internally myself in the midst of computation, which may or may not work depending on the details of your system.  If I can't have or emulate a verifying system, then I cannot be Turing complete -- I'm just guessing at solutions.

Given that popular consensus is that such a verifying system implemented could not guarantee both returning in finite time AND returning an accurate answer, it would appear no, although we might be able to approximate it a reasonable percentage of the time.


Counting nodes in a trie I'm studying random tries in one of my classes, and was wondering if anyone could offer any guidance regarding a problem.

Question:
Given a random $m$-ary trie with $n$ total leaves, letting $I$ be the number of internal nodes in the tree (that is, nodes which aren't a leaf), show that $E(I)$ is $O(n)$.

About the distribution:
We have an alphabet of $m$ letters (hence an $m$-ary trie), each with a corresponding probability $p_i$. We randomly create $n$ words of infinite length by drawing the first letter from our distribution, the second letter, etc. Finally, we insert these $n$ infinite words into a $k$-ary trie. This trie will be infinite in length, but we prune it by removing any paths which are traversed by only one of our $n$ words, to eliminate 'redundancy'.

Attempt: I tried relating things back to the size of the random trie, which I call $S$. Every non-root node in the trie is the child of some internal node, so $mI = S-1$

That is $E(I) = E\left(\frac S m\right) - \frac 1 m$

So if I can show that the expected size of a random trie is O(n) I'm golden. But unfortunately everything we've covered in class relates to expected depths and heights of a given trie, and I don't have any ideas moving forward. Could anyone offer advice on what might be useful here?

If you don't have any degree-1 nodes in your trie (which is a tree) than you have more leaves than interior nodes. So in this case you have $I\le n $.

It depends a bit how you define the trie whether you can have many interior degree-1 nodes. If you study a compressed trie the all the path of degree-1 nodes are merges to an edge, so you are done. For an uncompressed trie, I am afraid, you can have many degree-1 nodes. Say you have one letter $a_i$ that is very common and has a high probability of $1-\varepsilon$ and $\varepsilon\in \Omega(1/n^2)$. Then your trie contains many long degree-1 paths with high probability. In this case the you can have more than $O(n)$ interior nodes. Please do the computations by yourself (you might choose a smaller $\varepsilon$ if you like).


Definition of 2-CNF (a.k.a Krom) formula In my lecturer's notes, the following definition for a 2-CNF wff is given:

  A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has at most two literals.

However, there is no mention in the notes of how one might represent clauses containing a single literal L in the wff's corresponding implication graph (although I suppose one could add an edge from every other literal to L). Looking at Krom's original paper, the definition he seems to use is:

  A 2-CNF formula, or Krom formula is a CNF formula F such that every clause has exactly two literals.

This definition would seem to make a lot more sense. Which definition is correct? Am I missing something?

A unit clause of the form $p$ is the same as the clause $p \lor p$, and so corresponds to the arrow $\lnot p \to p$.

As an example, consider the unsatisfiable CNF
$$ p \land (\lnot p \lor q) \land \lnot q. $$
The implication graph contains the following edges:
$$
\lnot p \to p \\
p \to q,
\lnot q \to \lnot p \\
q \to \lnot q
$$
These can be arranged in a cycle:
$$
\lnot p \to p \to q \to \lnot q \to \lnot p
$$
This cycle contains both $p$ and $\lnot p$ (and also both $q$ and $\lnot q$), showing that the formula is unsatisfiable.


Why don't imperative languages like C or Go support Haskell-like parametric polymorphism? Why don't imperative languages support parametric polymorphism as powerful as whats in Haskell and OCaml?

More specifically if I call a function foo(x) that internally calls bar(x) which internally calls baz(x), what prevents the type of parameter x from being inferred all the way down?

Is it possible to design an imperative language (like C or Go) with this behavior or must the language be functional?

Question: Does there exist a type system allowing for parametric polymorphism as powerful as Hindley-Milner, but suited for imperative languages and not functional languages.  If such a type system exists what are it's advantages and disadvantages?  I'm wondering if it can be done rather than why it hasn't been done.

The real answer is that the designers of those languages chose not to include it.

It's certainly technically possible. As has been said in the comments, Rust does, Java does, C# does, etc. However, there are some difficulties.

The first is in the choice of impelemtation strategy. Polymorphism is easy if you're working with Lambda Calculi and looking only at what reductions work. But when you want actual code that runs on a machine, there are two main strategies, each with their own tradeoffs:

Monomorphization: For each specialization of your polymorphic function that's used, you make a specialized copy of it in the machine code emitted. This option is great when you're using a language that actually emits machine code, and tends to be fast, since you can optimize the different versions of your code. But, it tends to increase the size of your program.
Pointers: The main reason you can't just use a function polymorphically is that you might give it arguments of different size, so when it's looking things up on the stack, it doesn't know their offsets. But if you always give it pointers to its arguments, then it can lay things out nicely. This way is simpler, but has slowness from an extra layer of indirection.

As for why the particular languages didn't use it, for C it's mostly historical. It wasn't really a mainstream thing when it was made, and it hasn't made its way into the main language. For Go, the decision has been quite controvertial, but again their main goals were simplicity, concurrency and code whose performance was easy to reason about.

Also, polymorphism breaks type soundness in the presence of mutable variables, which is why Rust only allows polymorphic functions, and ML has the value restriction.


Algorithm to check the 2∀-connectness property of a graph A graph is 2∀-connected if it remains connected even if any single edge is removed. Let G = (V, E) be a connected undirected graph. Develop an algorithm as fast as possible to check 2∀-connectness of G.

I know the basic idea is to build a DFS searching tree and then check each edge is not on a circle with DFS. Any help would be appreciated.

What I expect to see is a detailed algorithm description(especially the initialization of needed variables which is obscure sometimes), complexity analysis could be omitted.

A simple algorithm is the following:

Let $G = (V,E)$ be the graph you want to check for 2-connectivity.

  For each edge $e = (x,y) \in E$, look if there is a path from $x$ to $y$
  in $(V, E \setminus \{e\})$. If for some $e$, there is not such a path, the graph is
  not 2-edge connected. If there is such a path for each $e$, $G$ is
  2-edge connected.

You should also note, that this algorithm is not the fastest, but very easy to understand. The path-finding part can be done using for example BFS or Dijkstra's Algorithm.

This article also shows a simple algorithm for testing 2-edge connectivity, which runs in linear time.


Is the union of finite and infinite sequences over alphabet of length 1 countable? Is the union of finite and countably infinite sequence over alphabet $\Sigma=\{1\}$, countably infinite as well?

I understand this is similar a question to the one of finite and countably infinite strings over $\{0,1\}$, however I think that the previous argument is not valid in this case.

Now, countably infinite strings over $\{0,1\}$ can be of any kind, e.g.

$$e_i \in \Sigma^*, e_i=100000...$$
$$e_k \in \Sigma^*, e_k=110000...$$

However, I noticed that if I pose the same question with an alphabet of a character only, say $\{1\}$, there is only 1 infinite sequence that I can generate $11.....$, hence:

$$S = \Sigma^* \cup \{111..\}$$

From this assumption, I could map $0$ to the infinite $11...$ and assume that this set S is uncountable. Is this a valid argument? Can someone help me formalize this?

You haven't defined what you mean by "finite or countably infinite sequence" over an alphabet $\Sigma$, so let me assume that a "finite sequence" is a word over $\Sigma$, while a "countably infinite sequence" is an $\omega$-word over $\Sigma$, that is, a mapping from $\omega$ (the set of natural numbers) to $\Sigma$.

In your case, there is exactly one word of each length $0,1,2,\ldots,\omega$, so the set of "finite and countably infinite sequences" is countable, since the set $\omega + 1 = \omega \cup \{\omega\}$ of possible lengths (which is in one-to-one correspondence with the possible "finite and countable infinite sequences") is countable.

If you want to be very formal, you can show that $\omega + 1$ is countable by giving an explicit bijection between $\omega$ and $\omega + 1$, such as
$$
0 \mapsto \omega, \quad n+1 \mapsto n \text{ for all } n \geq 0.
$$


Computer Program vs. Algorithm It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and
a computer program is also a sequence of instructions to perform a (some) tasks with computer.

Then what makes a program different from an algorithm? is it a type of algorithm too?

In fact, I look for formal definitions for an algorithm and a computer program so I can distinguish them from each other or identify algorithms within a program.

Update:I have noticed in  Wikipedia by an informal definition (at least syntactically) any program is an algorithm.

  An informal definition could be "a set of rules that precisely defines a sequence of operations." which would include all computer programs, including programs that do not perform numeric calculations. Generally, a program is only an algorithm if it stops eventually.

I'm going to give the same answer as I gave the previous time this question came up.

First, understand that there is no good formal definition of "algorithm" at the time of writing. The key word here is "formal".

However, there are smart people working on it.

What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".

A mathematical function is formal notion of a mapping from inputs to outputs. So, for example, "sort" is a mapping between a sequence of orderable items and a sequence of orderable items of the same type, which maps each sequence to its ordered sequence. This function could be implemented using different algorithms (e.g. merge sort, heap sort). Each algorithm, in turn, could be implemented using different programs (even given the same programming language).

So the best handle that we have on what an "algorithm" is, is that it's some kind of equivalence class on programs, where two programs are equivalent if they do "essentially the same thing". Any two programs which implement the same algorithm must compute the same function, but the converse is not true.

Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function.

The hard part in all this is trying to capture what we mean by "essentially the same thing".

There are some obvious things that we should include. For example, two programs are essentially the same if they differ only by variable renamings. Most models of programming languages have native notions of "equivalence" (e.g. beta reduction and eta conversion in lambda calculus), so we should throw those in too.

Whatever equivalence relation we pick, this gives us some structure. Algorithms form a category by virtue of the fact that they are the quotient category of programs. Some interesting equivalence relations are known to give rise to interesting categorical structures; for example, the category of primitive recursive algorithms is a universal object in the category of categories. Whenever you see interesting structure like that, you know that this line of enquiry will probably be useful.


Bipartite Matching in the Plane I'm currently working on a problem that I came across:

  You are given a set $B$ of $n$ points in the plane, and a set $R$ of $n$ points in the plane. Each point is given by its coordinates. I have to Suggest an $O(n^{3})$ time algorithm for determining if there is a perfect matching between them, with the constraint that each point in $R$ is matched to a point in $B$ point whose distance is at most 1 unit away.

I have tried solving using the minimum distance using bipartite algorithm but could not arrive at a solution. Can anyone provide me with any ideas?

This problem has been solved by Alon Efrat, Alon Itai and Matthew J. Katz in their paper Geometry Helps in Bottleneck Matching and Related Problems. The running time of the algorithm is $O(n^{1.5} \log n)$.


How to do supervised learning without knowing the target I'm working on an optimization algorithm that I think could be considered machine learning, but I'm not sure.  Basically I have a model that I want to optimize by adjusting its parameters.  I don't have any target data to compare the output of my model to, so I don't know the loss factor.  However, I'm able to generate information on whether increasing or decreasing a parameter will improve my model.

This information consists of a sum of positive and negative numbers that I'll call votes, and they are very noisy.  I know I should increase the parameter if the average vote is positive and decrease it otherwise.  I can generate as many votes as I like if I invest the computational resources, and I need to generate a sufficient number to over come the noise.  I only know I've optimized the parameters if the average votes are zero.

I'm having a hard time optimizing my algorithm.  Basically it's hard to decide how many votes I should take before shifting the parameters, and then how much I should shift them.  I believe the optimal amounts depend very much on the circumstances.  I'm wondering if my algorithm falls under a class of optimization algorithms that have a literature I could research.  Or if anyone knows any literature that my be useful to what I'm working on.

It's hard to know what to recommend, without more context.

One possible approach is to use hill-climbing, simulated annealing, or some other form of local search.  A simple form of hill-climbing is to pick a random variable, determine whether increasing/decreasing it will improve your model, and if so, increase/decrease it; then repeat until no further improvement is possible.  You can combine with random restarts, or use a more powerful method like simulated annealing.

Alternatively, you could try using something like gradient descent.  Suppose you learn not only whether increasing the parameter will improve the model, but how much it improves it.  If you have this information, you can estimate the gradient at a point, then move in the direction of the gradient, and repeat.  Based on experience with stochastic gradient descent, rather than repeating this many times at a single point and averaging, it's likely to be more effective to do this only once at each point and instead repeat for more iterations of gradient descent (perhaps with a smaller step size).  Basically, because your information is noisy, each step is mostly random and is only loosely correlated with the correct direction, so this does a random walk that is slightly more likely to go in a good direction than a bad direction; after sufficiently many iterations, this should converge to a good solution.  The analysis of stochastic gradient descent shows that in many settings this performs better than trying to compute many votes at a single point, average them to get a very good estimate of the direction to go, and repeat for many fewer iterations.  So, the theory says: take only one vote.  There's no theory to tell you how much to change the parameters (the step size).  Usual practice in the machine learning literature is to treat this as a hyperparameter, try multiple different values (e.g., 0.0001, 0.001, 0.01, 0.1), and see which works best.  Sometimes it may be helpful to start with a large step size and then reduce it after some number of iterations.  There are also heuristic optimizers that try to adaptively adjust the step size, such as the Adam optimizer, but it's unclear whether they help or not.

Another approach is to use Bayesian optimization, which uses machine learning to construct a surrogate model that can predicts how well any set of parameters will perform, and then uses optimization methods on the surrogate model.  See, e.g., Google Vizier for one representative of this approach.

I can't predict which approach is likely to be most suitable to your setting.  That may depend on the number of dimensions (how many parameters you have), the dependence of the metric you care about as a function of the parameters (how nonlinear it is), and what kind of information you receive about any set of parameters.

Related: What solution to apply for finding the optimal parameters?, What is an appropriate global optimization technique for a noisy and expensive function?, Mathematical optimization on a noisy function.


How does one deduce small step operational semantics? This question arises from my reading of "Types and Programming Languages" (WoldCat) by Benjamin C. Pierce.

For the small step operational semantic evaluation rules for the arithmetic expressions (NB) in Figure 3-2 on page 41, there is the rule

  $pred\;(succ\;nv_1)\rightarrow\;nv_1$

My understanding is that it is to keep out invalid input like

  $pred\;(false)$

but how did he come to that exact syntax for the rule? Is there some algorithm that is used to massage the rules into the necessary form? Is there some book or paper that explains how to formulate rules for small step operational semantics?

Note: I am aware that there is a forum dedicated to questions for the book here.

Devising an operational semantics of a programming language requires ingenuity, just like engineering a new car does. Nevertheless, there are some principle and correctness criteria by which we can judge whether a given semantics is "good".

For example, a good operational semantics should make sure that "valid programs do not do bad things". In practice this translates to "if a program succesfully compiled it is not going to dump core when we run it". Some languages are unsafe in this respect (C/C++), some are designed with safety in mind (Java, Python), and some are proved to be safe (Standard ML).

One way of translating "valid programs do not do bad things" is to interpret "valid program" as "well typed program" and "bad thing" as "getting stuck during evalution, even though we have not reached a final value". For this to make sense you have to define what "well typed" and "value" means. The central theorem then is

  Safety: If a program $p$ has type $\tau$ then its evaluation diverges or terminates in a value of type $\tau$.

The theorem is typically proved by combining two lemmas:

  Type preservation: If $p$ has type $\tau$ and $p \mapsto p'$ then $p'$ has type $\tau$. Remember this as "types do not change during evaluation".

  Progress: If $p$ has type $\tau$ then it is either a value or there is a program $p'$ such that $p \mapsto p'$.

On the other hand, it does not matter what the operational semantics does with senseless programs, such as $\mathtt{pred}(\mathtt{false})$ because those do not have a type. It is the combination of typing and operational semantics that ensures safety. You cannot ensure safety just with the operational semantics, unless you are willing to make bizarre evaluation rules that will make your language awfully hard to debug.


Computing number of ways to make change Given a list $C=[c_1,c_2,\dots,c_k]$  of positive integers, representing the values of $k$ varieties of coins, and a positive integer $n$, let $f(n,C)$ be the number of handfuls of coins with total value $n$. The order within the handful does not matter, and there is an infinite supply of each variety of coin.
What is the state-of-the-art algorithm to compute $f(n,C)$?

Equivalently, $f(n,C)$ is the number of ways to choose non-negative integers $x_i$ so that $n=\sum_{i=1}^k x_ic_i$.
The list $C$ can have repeats, and the interpretation is that there are two varieties of coin with the same value. For example, $f(3,[2,1,1])=6$. Letting $A$ and $B$ be the coins of value $1$, and $C$ be the coin of value $2$, the $6$ possible handfuls are
$$
(A,A,A),(A,A,B),(A,B,B),(B,B,B),(A,C),(B,C)
$$
I can think of two solutions. Which is faster depends on $n$ and $C$.

Dynamic programming: Let $C'$ denote $C$ with its last entry removed. A use-it-or-lose-it argument gives $$f(n,C) =  f(n-c_k,C)+f(n,C') .$$ This lets you compute $f(n,C)$ by filling out an $n\times k$ DP table, which takes $$\boxed{\Theta(nk)}$$ additions and look-ups.

Matrix exponentiation: I will illustrated in the case $C=[2,3,4]$. Letting $a_n=f(n,C)$, then $a_n$ satisfies the recurrence (see https://cs.stackexchange.com/a/87810/24590)
$$
a_n = a_{n-2}+a_{n-3}+a_{n-4}-a_{n-5}-a_{n-6}-a_{n-7}+a_{n-9}
$$
Any linear recurrence can be solved by computing the $n^{th}$ power of a certain matrix. In this case, the recurrence has order $c_1+\dots+c_k$, so this algorithm takes
$$
\boxed{O(\log n \cdot M(c_1+\dots+c_k))}
$$
arithmetic operations, where $M(k)$ is the number of arithmetic operations required when multiplying two $k\times k$ matrices (naively $M(k)=k^3$, state of the art is $k^{2.3728639}$).  We get $\log n$ by using exponentiation by squaring.

The second algorithm is asymptotically much better as $n\to\infty$, but the first is better when the sum of $C$ is large.

Are there any known faster algorithms?

From a theoretical perspective, you can diagonalise (well, decompose to Jordan normal form) to do the matrix power. It costs $O(M(c_1+\dots+c_k))$ to decompose, $O(\log n \cdot (c_1+\dots+c_k))$ to raise the diagonal matrix to the $n$th power, and $O(M(c_1+\dots+c_k))$ to finish up.