Shortest path with exactly $k$ edges From Skiena's book The Algorithm Design Manual, chapter 6, problem 22:

Let $G = (V,E,w)$ be a directed weighted graph such that all the weights are positive. Let $v$ and $u$ be two vertices in $G$ and $k \leq |V|$ be an integer. Design an algorithm to find the shortest path from $v$ to $u$ that contains exactly $k$ edges. Note that the path need not be simple, and is permitted to visit vertices and edges multiple times.

This is not homework, its me preparing for an interview. I have no clue how to approach this.

Since you allow non-simple paths(i.e. walks), seems like a dynamic programming algorithm will work.

For each $1 \le m \le k$, and every vertex $u$, we compute $D[m,u]$ where $D[m,u]$ is the weight of the shortest walk of length exactly $m$ starting at $v$ and ending at $u$. We are looking for $D[k,w]$.

This can be computed as

$$D[m+1, u] = \min_{x \in Pred(u)}\{D[m,x] + w[x,u]\}$$

Where $Pred(u)$ (predecessor) is the set of vertices which have an outgoing edge to $u$ and $w[x,u]$ is the weight of edge $x\to u$. You start with $D[1,u] = w(v,u)$ (allowing $\infty$).

You can add auxiliary structures to find the actual walk.

Running time: $O(k |E|)$.

This is because for each number of required edges from 1 to k, we go through the indegree of each vertex and in total, we visit all $|E|$ edges. We visit all $|E|$ for each number of the required edges ($k$) so the final run time is $O(k |E|)$ .

btw, if we wanted only simple paths, then this is probably $NP$-Hard, as we can set $k=n$ and reduce some variant of Hamiltonian Path problem to it.


Why the Cook-Levin reduction is not a parsimonious reduction? In the textbook Arora-Barak, after presenting the Cook-Levin theorem's proof the authors say that the proof can be modified slightly to make the reduction parsimonious. The parsimonious reduction is one in which certificates of an NP language are mapped bijectively on the certificates of SAT. I am not sure why the reduction is already not parsimonious.

The reduction basically converts the snapshots $Z_1, Z_2, \dots, Z_{T(n)}$ ($Z_i$ contains the state, the symbols of the two tapes currently under head in the $i$th step) of an oblivious NP machine into a SAT formula, where $T(n)$ is the runtime of the NP machine. The main observation used for converting the sequence of snapshots into a SAT formula is that every $Z_i$ is a function of previous $Z_i$s.

Following is Cook-Levin's proof from Arora-Barak.

The string $u$ is the certificate for $x$ with respect to $L$ and $M$, while the string $y \circ z$ is the certificate for $\phi_x$ with respect to $SAT$ and a verifier TM for SAT. $M$ is an oblivious deterministic TM with two tapes - an input tape and a work/output tape. Although I did not find this clearly stated anywhere, it seems reasonable to assume that the output of $M$ is 1 if the final state is $q_{halt}$, and the contents of the output tape are $1 \Box \Box \ldots$, and the heads are positioned at their initial locations at the left ends of the tape. In Garey and Johnson, the formalization of the Turing machine contains two halt states $q_Y$ for accept, and $q_N$ for reject, all other states are designated non-halting - using such a formalization could simplify this reduction; however, Arora and Barak have kept things more general by not focussing on Boolean functions, since the scope of their text is larger.
Any certificate $u$ can be mapped to some certificate $y \circ z$ such that $y = x \circ u$, and $z$ equals the snapshots of $M$ - this map is clearly injective. Similarly, $y \circ z$ may be mapped to $u$ by extracting the appropriate substring - in this case, let us prove that the map is injective. Assume that two certificates $y_1 \circ z_1$ and $y_2 \circ z_2$ may be mapped to the same certificate $u$. This implies that $y_1 = y_2 = x \circ u$, which in turn implies that $z_1 = z_2$ since these strings record the $T(n)$ snapshots of the deterministic TM $M$ starting for the same input $y_1 = y_2$. Given these two injective maps, we can infer that the two sets of certificates have the same cardinality, and hence the reduction is parsimonious.
However, the authors seem to think otherwise. Excercise 2.13.a asks the reader to make the reduction parsimonious, and even a hint is provided:

"Modify the machine M so that it clears up its work tape before
outputting a 1 and moves both heads to one end of the tape. Then the
final snapshot and head locations are unique."

Note that the suggested modification does not affect the reduction at all! Using our definition of output, we are already assuming that $M$ is doing everything the hint suggests. The only issue I can see is that Condition (4) only examines the last snapshot $z_{T(n)}$ to determine whether the output was 1 but $z_{T(n)}$ only captures a small portion of the output tape - I would question whether this is an accurate test for whether $M$ halted and produced the output 1 - that is, I am not sure that the reduction given in the text is correct.


Singleton in a simple SBM I can't work out the solution to the following exercise:

We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are in the same cluster and $q$ otherwise. This is a simple SBM with $2$ clusters. The problem ask to show that if $(p+q) << \log(n)/n $, the probability of having a singleton in the realization of this SBM goes to $1$ has n goes to infinity.

Here $(p+q) << \log(n)/n $ means that $f(n) = p(n) + q(n)$ has a function of $n$ satisfy $\underset{n \rightarrow \infty}\lim \frac{f(n)}{\log(n)/n} = 0$.

I've been trying the following approach. Let $S$ the event we are interested in and for any vertex $i$ let $X_i$ be the indicator random variable of the event $i$ is singleton. Define $X = \sum_{i} X_i$, then $\mathbb{P}(S) = 1 - \mathbb{P} (X = 0)$. Since $X$ is non negative, then $\mathbb{P} (X = 0) \le \frac{\text{Var}[X]}{(\mathbb{E}[X])^2}$.

In addition, I observe that since $X_i$ is binary valued, then $\text{Var}[X_i] \le \mathbb{E}[X_i^2] = \mathbb{E}[X_i]$. So

$$\text{Var}[X] \le \mathbb{E}[X] + \sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j]$$

Computing all the terms I get:

$$\mathbb{E}[X] = 2n(1-p)^{n-1}(1-q)^{n}$$
$$\sum_{i}\sum_{j \ne i}\text{Cov}[X_i, X_j] = n^2q(1-p)^{2n-2}(1-q)^{2n-1} + n(n-1)p(1-p)^{2n-3}(1-q)^{2n} \le n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)$$

For the convariances, I've split the cases when $i$ and $j$ are in the same cluster and when $i$ and $j$ are in different clusters.

All in all, I get:
$$\frac{\text{Var}[X]}{(\mathbb{E}[X])^2} \le \frac{2n(1-p)^{n-1}(1-q)^{n} + n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)}{4n^2(1-p)^{2n-2}(1-q)^{2n}}$$

This term doesn't look quite right for what I'm supposed to prove, does it?

This answer shows an approach to the problem in the question.

(Threshold of isolated vertices) Let $G(n,p)$ be a random graph with $n$ vertices and each edge is present with probability $p$ independently. Suppose that $p\le c{\log n}/n$ for some constant $c$. Then the possibility of the appearance of at least one isolated vertex in $G(n, p)$ goes to 1 when $n$ goes to infinity.

Assume the above proposition on the threshold of isolated vertices holds. Applying it to the case of $G(2n, p+q)$ where $p+q\le c \log (2n)/2n$, we know the appearance of at least one isolated vertex goes to 1 when $2n$ goes to infinity.

Since the random graph in the question has less edges than the random graph above, the appearance of at least one isolated vertex in the random graph in the question also goes to 1 when $n$ goes to infinity. (This loose argument can be made rigorous.)

If you prefer not to use that proposition, you can transplant its proof to fit the current problem. It should not be hard to find a proof for that proposition since it is a classic result in the introductory theory of random graphs.


Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set Note: overline denotes complement

I am trying to show that $\overline{\text{HALT}'}\leq_1 \{i\colon\Phi_i=\Phi_e\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't figure out where I'm going wrong. I am using the construction of the proof of Rice's theorem to prove this and I thus do the following:

Let $e_0\colon \Phi_{e_0}\uparrow$. We thus have that, as long as $\Phi_e\downarrow$, $e_0\in\overline{A}$. Now choose $e_1\in A$ and define $s$ such that $$
 \Phi_{s(x)}(y) = \begin{cases}
 \Phi_{e_1}(y),& \text{if } x \in \text{HALT},\\
 \text{undefined},& \text{if } x\not\in \text{HALT}
 \end{cases}
 $$
we thus get that $x\in\text{HALT}\implies s(x)\in A$ while $x\not\in\text{HALT}\implies s(x)\in\overline{A}$ and it follows that $\text{HALT}\leq_1 A$ and $\overline{\text{HALT}}\leq_1\overline{A}$.

This is, however, the opposite of what I want but I can't seem to see where I'm going wrong? Any help would be greatly appreciated!

Let $e$ be and index for the constant 0 function. Then consider $s$ such that

$$ \varphi_{s(x)}(y) = \begin{cases} 0 & \mbox{ if }\varphi_x(x) \mbox{ does not halt within $y$ steps} \\ 1 & \mbox{otherwise} \end{cases} $$

Then $\varphi_{s(x)} = \varphi_e$ if and only if $x \not\in HALT$ (assuming HALT was the diagonal halting problem).

The function $s$ can be choosed to be monotonic (use pumping), hence it is one-to-one.


compressing a set of binary strings with fixed length I'm looking for a data structure / algorithm to store an unordered set S of binary strings of a fixed length n (i.e. all matching the following regular expression: [01]{n}).

Insertion and lookup ("Is element x in the S?") should maximally take polynomial time to |S|.

The space complexity should be logarithmic to |S| for large sets. In other words, the space should not be exponential to n if for example 2^n / 2 random and unique strings are inserted, but polynomial to n.

Is such a thing known to exist?

Suppose $S$ consists of $m$ strings in $\{0,1\}^n$ and we don't allow query arrows. Any two different sets $S_1,S_2 \subseteq \{0,1\}^n$ of size $m$ respond differently to some lookup query: there must be some $x \in S_1\setminus S_2$, for example, and the lookup of $x$ should succeed in $S_1$ and fail in $S_2$. For this reason, the contents of your data structure should be different for $S_1,S_2$. Since there are $\binom{2^n}{m}$ different choices for $S$, any data structure supporting all of them should have at least $\binom{2^n}{m}$ different settings. In particular, if you use $M$ bits to store it then $2^M \geq \binom{2^n}{m}$. When $m = 2^n/2$, for example, this forces $M \geq 2^n - O(n) = 2m - O(\log m)$.


Evaluating two different Algorithms, which one will scale better? I'm evaluating two different algorithms to choose one for my implementation, they just do calculations on top of arrays, get some input of $n$ elements, and produce some output of $m$ elements, and I'm looking for an opinion about which one will scale better.

The output they provide given the input is exactly the same on both cases, the computation time for the second is slightly better, maybe a 20%...

As I have the code from both, I have been able to get some counts out of the main loop, where the processing happens (they are iterative).

The first Algorithm behavior reminds me a lot merge sort, for a input $n$, every iteration just process half of the elements, so for $n=4000$ each iteration process half of the elements until there is no more $i_1=2000,i_2=1000,i_3=500,...,i_x=1$

The second Algorithm is just linear, I did the same count thing, and with input $n=4000$, looks like it just process $\approx n/c$ (some $c$) elements per iteration, so $i_1=266,i_2=266,i_3=266,...,i_x=266$

(They do not depend on the numerical values in the input)

Which one will you choose?

You are not looking for asymptotic behaviour, but for actual runtime for rather large n; you determine how large.

You can either analyse both algorithms, and estimate what their run times will be, or much easier, you can measure it. You have to be very careful if you do this with an optimising compiler, because they tend to throw away operations if they can prove they are not actually used. But done carefully, this will give you the actual numbers.

Draw some graph showing the runtime depending on N. And be aware that different processors or different compilers can produce rather different results. Also be aware that if the time "jumps" for certain sizes of n, lets say 50n nanoseconds if n < 10,000, 100n nanoseconds if n < 1,000,000 and 200n nanoseconds if n > 1,000,000 then your time may be depending on memory access, and you can often improve time significantly be re-arranging operations.


How is quantum function $f(x) = a^x \mod N$ constructed in Shor's algorithm? I can't see how I can apply quantum function $a^x\mod N$ to initial states. Explanations of Shor's algorithm often skips this part, and I do not see what unitary matrix this algorithm would correspond to.

reference: https://en.wikipedia.org/?title=Shor%27s_algorithm

This paper by Pavlidis and Gizopoulos walks through one possible construction of the circuit you're looking for and also provides references to other literature on the subject:

"Fast Quantum Modular Exponentiation Architecture for Shor's Factorization Algorithm". Archimedes Pavlidis, Dimitris Gizopoulos.  http://arxiv.org/abs/1207.0511


What is the time complexity of the Bailey–Borwein–Plouffe formula? How can I assess and derive the time complexity of the BBP formula?
$$
BBP(n)=4S(1,n) - 2S(4,n) - S(5,n) - S(6,n)
$$
where

$$
S(j,n) = \sum_{k=0}^n{\frac{16^{n-k}mod(8k+j)}{8k+j}}+\sum_{k=n+1}^{\infty}{\frac{16^{n-k}}{8k+j}}
$$

Note that the modulo is evaluated using the binary modular exponentiation algorithm (which is supposedly O(log N)) and the second sum iterates only over a few elements, i.e. up to a certain $\epsilon$.

I got O(N log N), but even if it is correct, I can't derive it.

A good place to start is the BBP paper. In Section 3 (1st paragraph of page 8) they state that the running time for $n$ digits is $O(n\log nM(\log n))$, where $M(m)$ is the complexity of integer multiplication; currently the best known algorithms give $M(m) = O(m\log m 2^{O(\log^* m)})$ bit complexity, though Fürer himself (inventor of the first algorithm with that complexity) argues that this is not the correct complexity measure.


Mod 2 is primitive recursive Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive.

My attempt is as follows

$$ E(x) = x \mod 2$$
To show that any function is primitive recursive, it must be obtained by composition and recursion from the initial functions $s(x) = x + 1; n(x) = 0$ and $u_i^n(x_1,x_2 \ldots x_n) = x_i$
We know that
$$ E(0) = 0 $$
$$ E(x+1) = (E(x) + 1) \mod 2 $$
By using induction -
$$ E(n) = n \mod 2$$
Let $n = 0$
$$ E(0) = 0$$
which is easily shown to be primitive recursive since it is an initial function of the $PRC$ class.
Assuming that this is true for $n = k$.
$$E(k) = k \mod 2$$
Taking $ n = k+1 $
$$ E(k+1) = (E(k) + 1)\mod 2 $$

But at this point, I do not know how to proceed.

Define a function $a(x)$ by primitive recursion as follows: $a(0) = s(0)$ and $a(x+1) = 0$. In particular, this function satisfies $a(0) = 1$ and $a(1) = 0$. Now we can define $E(x)$ by primitive recursion: $E(0) = 0$ and $E(x+1) = a(E(x))$. You can prove that $E(x)$ works by induction (left to you).


Clustering a set of images using keypoint descriptors I'm trying to cluster around 16000 images into ~200 clusters, using kmeans with metric as euclidean distance or cosine distance. I understand that i need to extract keypoint descriptors to compute features for each image. I'm looking at SIFT as an option but, SIFT outputs different number of keypoints for each image that i have. How can i use these keypoint descriptors generated by SIFT to make a uniform sized feature vector for every image, so that i can feed these vectors to kmeans. Or should i use any other feature descriptor apart from SIFT?

I don't know how to do it that way.  I would suggest you do it a different way:

Define a distance metric that measures the dissimilarity between two metrics.  In particular, if $I,J$ are two images, $d(I,J)$ should quantify how dissimilar $I,J$ are -- large values indicate they are very different, small values indicate they are very similar.
Use a different clustering algorithm that only needs a distance metric.

For #1, there are many ways of measuring/computing image similarity.  If you want to use SIFT as your starting point, you can align the two images and compute some metric based upon the number of keypoints that are well-matched ("inliers") vs the number that aren't ("outliers).

For #2, there are many options.  One option is to use hierarchical clustering.

I recommend you spend some time reading through the research literature on measuring image similarity in the computer vision literature.  There's lots of work, and many methods proposed and evaluated.

See also https://stackoverflow.com/q/843972/781723 and https://stackoverflow.com/q/4196453/781723.  You could also use the TinEye API.


Inverse Reinforcement Learning and Apprenticeship Learning differences IRL as I understand is where the AI is given a policy from an "expert" and needs to solve for the reward function which best fits the policy.

And Apprenticeship Learning via IRL was explained as an expert demonstrating a skill and the reward function also has to be derived using the expert behavior.

I don't necessarily understand the difference between the two since apprenticeship learning directly uses IRL. Any explanation of differences would be helpful.

Apprenticeship Learning uses Inverse Reinforcement Learning and there is a subtle difference between the two. Inverse Reinforcement Learning tries to recover the reward function ($R^*$) from demonstration trace of a teacher (an expert at the task being solved). Finding the optimal policy ($\pi^*$) from that "guessed" reward is what is meant by Apprenticeship Learning. More information on this link.


LOGSPACE in different Turing Machine variants Let's consider two-head (and two tapes) Turing machine. Let some problem $P$ be decidable in $LOGSPACE$ on that machine. What about complexity of that problem on the normal Turing machine ( one head, one tape?)

I asked that question because I am thinking of some problem- I have to be able to get value of $i$-th cell but my input is read-only.

Let T(n) be the time complexity of problem on two tapes Turing machine then time complexity on single tape Turing machine is going to $O(T(n)^2)$ (more precisely $10 \times T(n)^2$). You have mentioned that your problem is in $LOGSPACE$, So $T(n)$ will be going to be some polynomial in $n$. To simulate two tapes Turing machine by single tape encode locations 1,3,5,7... to encode the first tape and locations 2,4,6... to encode second tape and also use symbol for the encoding of head positions. Now to simulate the one movement of two tape Turing machine you need to first find the head position (swap left to right) so you need $O(T(n))$ steps. Now to simulate the $O(T(n)$ many steps you need $O(T(n)^2)$ time.


Of which Chomsky-type is the language $L = \{a^jb^ic^{2i} | i,j \in \mathbb{N}^0\}$? At first I thought the language would be context sensitive because it seems that it can be shown with the pumping lemma for regular languages, that it's not a regular language and analogously with the pumping lemma for context free languages, that it is not context free. But it upon further pondering I came up with a pushdown automaton that would match this language. So I'm a bit at loss as to what type of language it is. I hope someone can help.

The language is context-free. You can use the pumping lemma for regular languages to show that it is not regular. However, you can construct a context-free grammar to show that the language is context free. For example, the following CFG grammar would generate it

$S \to A\ |\ aS  $

$A \to \epsilon\ |b A cc $


Why is Iterative-deepening A* optimal, even without monotonicity? Why is it that Iterative-deepening A* is optimal, even without monotonicity? How can I be sure that the first goal reached is the optimal one?

In a nutshell: IDA* traverses all paths of lengths iteratively larger and it stops only when expanding (as opposed to generating) the goal node with a cost such that all paths of an inferior cost have been already examined. Monotonicity (or consistency) is not required but admissibility of the heuristic function is a must if optimal solutions are required.

Now, how can we achieve that? It is simple. Get rid of the condition of monotonicity and pay attention instead to the condition of admissibility, i.e., $h(n)\leq h^*(n)$ where $h(n)$ is the heuristic estimate to reach the goal $t$ from node $n$ and $h^*(n)$ is the optimal cost of reaching the target. In other words, all that is required is that we have a function (i.e., $h(n)$) which provides a lower bound on the cost-to-go.

In the following bear in mind that IDA$^*$ is nothing more and nothing less than a depth-first search algorithm which prunes children that exceed a particular $f(n)$ value. As in the case of A$^*$, $f(n)=g(n)+h(n)$ where $g(n)$ is the cost of the path from the start state $s$ to $n$. All we have to do is to decide how to handle $f(n)$ while achieving our goal ...

Step 1: Since we have a lower bound to reach the goal, start IDA$^*$ with a threshold equal to $h(s)$, the heuristic estimate of the start state. This simply amounts to traverse all paths stemming from $s$ until a node $n$ is found such that $f(n) > h(s)$. This operation is necessarily finite in locally finite graphs (i.e., with bounded branching factor). While generating paths, note that you stop at those nodes $n$ that meet the aforementioned condition so that you can easily save the minimum excess over $h(s)$
Step 2: Once the first step is over, you know: first, no path of length $h(s)$ gets to the target; second, the next cheaper paths that can be traversed from $s$ have a cost equal to the minimum excess computed in the previous iteration. This is all you need. Proceed now as in Step 1 but using the minimum excess computed in the previous iteration as the threshold. If the iteration ended withouth success apply iteratively until getting to the solution.

Notice the remark I made in the first paragraph: from the behaviour of this algorithm, admissibility is guaranteed if you stop when expanding the goal node. This means that all paths of an inferior cost have been already traversed. If you ever stop when generating the goal, then you might incurr in suboptimal solutions since those paths might have a cost that exceeds the current threshold of that iteration.

In no place, consistency is required. From Steps 1 and 2, a proof of correctness can be easily derived by induction on the number of iterations.

Hope this helps,


What Are the Ideas Behind Variations of the Coin Change Problem? Problem: given a set of n coins of unique face values, and a value
  change, find number of ways of making change for change.

Assuming we can use a denomination more than once, here's the pseudocode I came up with

1. NUM-WAYS(denom[], n, change)
2.   dp = [change + 1][n + 1]
3.   for i = 0 to n
4      dp[i][0] = 1
5.   xs = denom.sorted

6.   for i = 1 to change
7.     for j = 1 to n
8.       if xs[j - 1] > i
9.         dp[i][j] = dp[i][j - 1]
10.      else
11.        dp[i][j] = dp[i - xs[j - 1]][j] + dp[i][j - 1]

12.  return dp[change][n]

The above algorithm is clear to me. However, if we are only allowed to use a denomination once, then line 11 changes to dp[i - xs[j - 1]][j - 1] + dp[i][j - 1], as if we are not allowed to use the current denomination at all. I'm failing to wrap my head around this. Can you explain this?

Here're some test runs:

Change: 3, denominations: [8, 3, 1, 2]
11111
01111
01222
01233

// use once
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
00111
00122

Change: 4, denominations: [3, 1, 2]
1111
0111
0122
0123
0134

// use once
Change: 4, denominations: [3, 1, 2]
1111
0111
0011
0012
0001

OP here, answering my own question for the greater good of mankind.

Let dp[i][j] denote the solution to the [i,j]-th subproblem; that is, dp[i][j] is the number of ways to make change for the amount i, using coins j through n.

Coin Change Problem with Repetition

dp[i - xs[j - 1]][j] + // 1
    dp[i][j - 1]       // 2

Use coin j, and since there is no constraint on the denominations, solve the smaller subproblem using the same denomination.
Don't use coin j.

Coin Change Problem without Repetition

dp[i - xs[j - 1]][j - 1] + // 1
    dp[i][j - 1]           // 2

Use coin j, and since we used coin j for this subproblem, we can't use it for any other.
Don't use coin j.


Algorithm to chase a moving target Suppose that we have a black-box $f$ which we can query and reset. When we reset $f$, the state $f_S$ of $f$ is set to an element chosen uniformly at random from the set $$\{0, 1, ..., n - 1\}$$ where $n$ is fixed and known for given $f$. To query $f$, an element $x$ (the guess) from $$\{0, 1, ..., n - 1\}$$ is provided, and the value returned is $(f_S - x) \mod n$. Additionally, the state $f_S$ of$f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

By making uniformly random guesses with each query, one would expect to have to make $n$ guesses before getting $f_S = x$, with variance $n^2 - n$ (stated without proof).

Can an algorithm be designed to do better (i.e., make fewer guesses, possibly with less variance in the number of guesses)? How much better could it do (i.e., what's an optimal algorithm, and what is its performance)?

An efficient solution to this problem could have important cost-saving implications for shooting at a rabbit (confined to hopping on a circular track) in a dark room.

First of all, I will assume that by

  Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

you actually mean

  Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly at random from $$\left\{- \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|, \ldots, -1, 0, 1, 2, \ldots, \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|\right\} $$

Otherwise, it is not entirely clear that $f_S \in \{ 0, ..., n-1\}$ always holds and how exactly $f_S \pm k$ behaves.

Using this, the problem basically comes down to "missing as much as possible". Observe that the closer we shoot the rabbit, the larger hops he makes; in the extreme case we have $f_S - x = \pm 1 \mod n$. This results in a uniform hop between $ -(\lfloor n/2 \rfloor \pm 1)$ and $ (\lfloor n/2 \rfloor \pm 1)$, which basically completely randomizes the position of the rabbit again. On the other hand, if we miss as badly as possible - by an offset of $f_S - x \mod n = \lfloor n/2 \rfloor$, the rabbit actually does not move at all (!) and the black box actually updates us on this fact. Therefore, we can just turn around and shoot the rabbit.

We are left with finding a procedure for missing increasingly in each shot. I propose a simple "binary search". (I will conveniently omit the rounding.) It proceeds roughly as follows:

Reset and shoot at an arbitrary position until you get from the blackbox the answer $(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$ This takes a constant amount of steps in expectation.
Now, we know that the rabbit's past position $f_S$, and that it did not move more than $\frac{1}{4}n$ steps in either direction. This basically halves our search space in the next iteration, since the rabbit has to be at a position $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
Recurse: Shoot at position $f_S - n/2 \mod n$. With probability $1/2$, the position $f_S'$ the rabbit jumped onto in step 1&2  lies the range $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$. In that case we halved the search space once more. With probability $1/2$, the rabbit did not jump in that range, but since we know that $f_S' - x \mod n = f_S' - f_S + n/2 \mod n \in \{ \frac{1}{2}n - \frac{1}{4}n, ..., \frac{1}{2}n + \frac{1}{4}n \}$, we have the same assumptions as in step (2) and therefore lose nothing.

Each step needs $2 = \mathcal{O}(1)$ expected time to succeed and halves the search space, yielding an overall of $\mathcal{O}(\log n)$ expected number of steps.


Minimal DFA for $1\Sigma^*0$ What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\{0,1\}$ which accepts those strings that start with 1 and end with 0?

The following answer assumes that each state in a DFA must contain an outgoing edge for each symbol. Otherwise, you might need one state fewer.
Let us say that two words $x,y$ are equivalent modulo $L$ if for any word $z$, either both $xz$ and $yz$ are in $L$, or both of them are not in $L$.
If two words $x,y$ are not equivalent modulo $L$, and $A$ is any DFA accepting $L$, then the state of $A$ after reading $x$ must be different from the state of $B$ after reading $y$ (why?).
As a consequence, if $x_1,\ldots,x_n$ is a collection of words, any two of which are not equivalent modulo $L$, then any DFA for $L$ must contain at least $n$ states.
(Furthermore, it is known that if the minimal DFA for $L$ contains $n$ states, then we can find $n$ such words: for each state, we take some word leading to it; but we don't need this direction here.)
In your case, the following words are pairwise inequivalent: $\epsilon, 0, 1, 10$. To show this, we need to consider all six pairs:

$\epsilon,0$ are inequivalent since $10 \in L$ but $010 \notin L$.
$\epsilon,1$ are inequivalent since $0 \notin L$ but $10 \in L$.
$\epsilon,10$ are inequivalent since $\epsilon \notin L$ but $10 \in L$.
$0,1$ are inequivalent since $00 \notin L$ but $10 \in L$.
$0,10$ are inequivalent since $0 \notin L$ but $10 \in L$.
$1,10$ are inequivalent since $1 \notin L$ but $10 \in L$.

This shows that every DFA for $L$ contains at least $4$ states. Conversely, there is a DFA for $L$ containing $4$ states, which I will let you figure out.


Showing strong connectivity is in DSPACE((logn)^2) $ST-CONN = \text{{(G,s,t) | G is directed graph, there's path from s to t}}$
I've learned the following deterministic algorithm to solve the problem in $log^2n$ space:
$\psi(G,s,t,k) :$
$\hspace{1cm}\text{if k == 1: return 1 if there's edge from s to t, else return 0;}$
$\hspace{1cm}\text{foreach } v \in V(G) \text{:}$
$\hspace{2cm}L=\psi(G,s,v,\lceil{\frac{k}{2}}{\rceil});$
$\hspace{2cm}R=\psi(G,v,t,\lfloor{\frac{k}{2}}{\rfloor});$
$\hspace{2cm}\text{if L == 1 and R == 1, return 1;}$
$\hspace{1cm}\text{return 0;}$
The professor said in class that the algorithm takes at most $\mathcal{O}(\log^2n)$ space, where $n$ is the number of vertices. But don't we pass the entire graph each call? I'll expect to see a $|V|+|E|$ factor in the big-oh, or maybe I miss something here.

You don't need to pass $G$ every time, since it doesn't change across calls. You can think of it as a global variable, which is stored only on the input tape. The other parameters take only $O(\log n)$ steps, and since the depth of the call stack is also $O(\log n)$, in total this uses up $O(\log^2 n)$ space on the work tape.


Height and depth of every node in Path Compression If we have an union-find(disjoint-set) data structure and we are doing an union by rank and path compression for a find operation, how would the depth and height of every node change after the find operation?

I am trying to find the amortized cost of the find operation using the potential function:

$$phi(x) = \sum_{x} height(x) $$

I know this is not the right potential function, however, i am trying to learn more about amortized analysis and i am just practicing by analyzing more data structures.

I assume that the height of a node $\small x$, denoted as $\small h(x)$, is recursively defined as:
$$
\small
h(x) = \begin{cases}
0 & \text{ if $x$ is a leaf} \\
1+\max\{h(y) \mid y\text{ is child of } x\} & \text{ otherwise }
\end{cases}
$$
Let the value of the potential function before calling $\small \texttt{Find}(x)$ be $\small \Phi$ and the value after the call be $\small \bar{\Phi}$. Similarly we can define $\small h(x)$ and $\small \bar{h}(x)$ respectively. Denote as $\small P_x$ the path from $\small x$ to the root $\small r$ of the corresponding tree. By path compression, nodes in $\small P_x$ (except $\small r$) are all set to point to $\small r$. Therefore, generally $\small \bar{h}(y) \leq h(y)$ for $\small y \in P_x$, since $\small y$ may have one child removed.

The amortized cost of $\small \texttt{Find}(x)$ is:
$$
\small
\mathcal{O}(|P_x|) + \bar{\Phi} - {\Phi} = \mathcal{O}(|P_x|) + \sum_{y \in P_x}\{\bar h(y) - {h}(y)\}
$$
where $\small |P_x|$ is the # of nodes in $\small P_x$ and $\small \mathcal{O}(|P_x|)$ is the actual cost of $\small \texttt{Find}(x)$. Now look at term $\small \bar h(y) - {h}(y)$, by the discussion above, its value is no greater than $\small 0$. Unfortunately, there are special cases where $\small \bar h(y) = h(y)$ for all $\small y \in P_x$. Therefore, what we can say about the amortized cost, using sum of heights as potential function, is the amortized cost is $\small \mathcal{O}(|P_x|)$, which is the same as the worse-case bound.


Do closure properties for languages go the other way? For example I know the union of 2 either decidable or recognizable languages is decidable or recognizable. But say the union of two languages is decidable, does this tell us anything about themselves?

No, it doesn't tell us much. Intuitively, union erases information; it's not normally a reversible operation.

So, for example, the union of a language with its complement is clearly decidable and recognizable, regardless of any category in which the language might or might not belong.


Class of Algorithms where finding output of algorithm can be aided by output of same algorithm given a similar input Sorry for the confusing title, but I'm trying to find out if a certain algorithm or class of algorithms fits this description. Given an algorithm A, computing A(x) can be computionally easier if A(g) is known, where g is close to x, and it's easier the closer g gets to x. So also, the amount of computation A has to do grows with respect to the size of the input.

You would also have to be able to calculate the output of A(x) given A(g), x-g, A(x-g). Does A exist for anything other than trivial artithemtic, and if so, is there an entire class of algorithms which A belongs to?

It can be algorithms which use initial guess, for example algorithms for finding roots and local minimums/maximum like Newton's method and gradient descend. Here g and x are functions, and g is close to x means that they have roots or local minimums/maximums in similar locations, so taking A(g) as initial guess, algorithm can converge faster to A(x).


Structural induction proof I need to prove the following:

reverse(append(zs, z)) = Cons(z, reverse(zs))

Where:

sealed abstract class IntList
case object Nil extends IntList
case class Cons(x: Int, xs: IntList) extends IntList

def append(xs: IntList, x: Int): IntList = xs match {
    case Nil => Cons(x, Nil)
    case Cons(y, ys) => Cons(y, append(ys, x))
}

def reverse(xs: IntList): IntList = xs match {
    case Nil => Nil
    case Cons(x, ys) => append(reverse(ys), x)
}

I've already made the induction basis:

Assume $zs=Nil$.
\begin{align*}
  reverse(append(zs, z)) &=reverse(append(Nil,z)) \\
                       &=reverse(Cons(z,Nil)) \\
                       &=append(reverse(Cons(Nil),z)) \\
                       &=Cons(z,reverse(Nil))
\end{align*}

How do I make the induction step?

Here is the complete proof:

reverse(append(Cons(w,ws),z)) =
reverse(Cons(w,append(ws,z))) =
append(reverse(append(ws,z)),w) =
append(Cons(z,reverse(ws)),w) =
Cons(z,append(reverse(ws),w)) =
Cons(z,reverse(Cons(w,ws)))

At one point we used the inductive hypothesis.


Efficient way to get integral points of segment from two points in grid I have two lattice (grid) end points of the line, how can I generate intermediate points of the line segment between them?
One way is iterate through all the x points or y points and check (solve line equation) if the coordinates we get each time are integral solution or not.

For a line segment defined by two integral lattice points $(x_0,y_0), (x_1,y_1)$ there will be $gcd(y_1-y_0,x_1-x_0)-1$ additional integral points along the line segment.
To find them move along line by largest value in the reduced slope.


Creating a Self Ordering Binary Tree I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the root being the most accessed node.

The professor gave me the BST and node struct to work with, but trying to get my head around the algorithm to update the tree as things are being inserted is confusing me.

I know that as the insert is happening, it checks if the current node's data is less or greater than the current node, then recursively goes in the correct direction until it finds a null pointer and inserts itself there. and after it is inserted it increases the priority by 1.

template <class Type>
void BinarySearchTree<Type> ::  insert( const Type & x, BinaryNode<Type> * & t )
{
    if( t == NULL )
        t = new BinaryNode<Type>( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++;  // Duplicate; do nothing for right now
}

Now I need to figure out when the node is equal, how to re-order the tree so that the current node (who is equal to an already existing node) finds the existing node, increases that node's priority, then shifts it up if the root is a lower priority.

I think I have the idea down that the AVL logic would work, and when a shift would take place, it would be a single rotation right or a single rotation left.

Here's where I'm confused,  don't really know where to start with creating an algorithm to solve the problem. Since the AVL algorithm works with keeping track of the balance of a tree, then rotating nodes left or right accordingly, this tree doesn't need to worry about being balanced, just that the nodes with the highest priority not have children with a higher priority.

Just two pointers:

If you want to actually combine the ideas of priority queues and binary search trees, think about combining heap and BST in one structure.
There is the concept of self-organising lists. The idea is to move recently accessed element to (or towards the) front in order to speed up future accesses to the same element, thusly "learning" the element distribution over time (with quality depending on the particular implementation). Maybe you can adapt this to trees?

Spoiler: Follow below links only if you have not been able to come up with something yourself.

   1. This is called a treap.
 2. Splay trees implement this idea.


Intersection of two shortest paths in connected weighted graph Let $G=(V,E)$ be a connected directed weighted graph with non-negative weights
on edges.  Let $u,v,s,t$ be vertices in the graph $G$. I need to find an algorithm which in $O(|E|\log |V|)$ time checks if there is a vertex $w$ which lies in the shorthest path from $u$ to $v$ and $s$ to $t$.

My idea is to find a shortest path from $u$ to $v$ using Dijsktra for example, and then for every vertex $w_i$ in that path check if there is a shortest path from $s$ to $w_i$ and $w_i$ to $t$. This can be done in the seeked time using Dijkstra if I am correct. Is my reasoning correct?

My idea is to find a shortest path from $u$ to $v$ ...

As noted by Pål GD, it is not enough to find just one shortest path from $u$ to $v$ as a different shortest path might contain the wanted intersection vertex. We have to take into consideration all shortest paths from $u$ to $v$. Since we are only interested in the vertices, it is enough to  find all vertices that are on some shortest path from $u$ to $v$. Denote that set of vertices as $S(u,v)$, where $S$ is the shorthand for both "shortest" and "set".

Characterization of $S(u,v)$: Let $d(x,y)$ be the distance between vertex $x$ and $y$. $$x\in S(u,v) \Longleftrightarrow d(u,x)+d(x,v)=d(u,v).$$

It is immediate to prove both "if" and "only if" part.

Here is an wanted algorithm.

Run Dijkstra's algorithm with $u$ as source and with a priority queue such as described at this wikipedia entry to obtain function $d_u$ such that $d_u(x)=d(u,x)$ for all $x\in V$ in the form of a look-up table. Similarly, obtain function $d_v(x)$ such that $d_v(x)=d(x,v)$ for all $x\in V$ by running Dijkstra's algorithm on $G$ with all edges reversed and $v$ as source. Similarly, obtain $d_s(x)$ and $d_t(x)$. For each vertex $x$ in $V$, check whether $d_u(x)+d_v(x)=d_u(v)$ and $d_s(x)+d_t(x)=d_s(t)$. If we find one such vertex, the answer is yes; otherwise, the answer is no.

Here are several related exercises.

Exercise 1. Prove the correctness of the characterization of $S(u,v)$ as well as the correctness of the algorithm.

Exercise 2. Show that the above algorithm runs in $O(|E|\log |V|)$ time when the priority queue of Dijkstra's algorithm is implemented as a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap.

Exercise 3. For each vertex $u$, let the shortest-path-index $d(u)$ be the number of ordered vertex pairs $(v_1,v_2)$ such that $u$ belongs to one of the shortest paths from $v_1$ to $v_2$. Let a path-center of $G$ be any vertex whose shortest-path-index is the maximum. Find an efficient algorithm that returns all path-centers.


Proving undecidability of the language composed of LBAs where their language is empty As it is explained in Sipser's book, the following language is undecidable and he proves this using the computation history method.

$\qquad E = \{\langle M \rangle \mid M\ \mathrm{LBA}, L(M)=\emptyset\}$

I wanted to see if we could use the same method used for proving undecidability of the following language in the case of LBAs too (instead of using computation history method).

$\qquad E' = \{\langle M \rangle \mid M\ \mathrm{TM}, L(M)=\emptyset\}$

Is it possible?

Consider the reduction that shows that LBA-emptiness is undecidable: you reduce from $\overline{A_{TM}}=\{<M,w>: M $ does not accept $w\}$.

So the reduction takes as input $<M,w>$, and outputs an LBA $T$ such that $L(T)\neq \emptyset$ iff $M$ accepts $w$.

Now, recall that an LBA is in particular a TM. So this same reduction actually outputs a TM, and actually shows that $E_{TM}$ is undecidable as well.

The reason this works is that the relationship between $E_{LBA}$ and $E_{TM}$ is such that if $M$ is an LBA, then $M\in E_{LBA}$ iff $M\in E_{TM}$. Since the reduction above always outputs an LBA, then you can just plug it in.


What is the polynomial time reduction between these two Hamiltonian cycle problems? Problem 1: Given an undirected graph, return the edges of a Hamiltonian cycle, or correctly decide that the graph has no such cycle.
Problem 2: Given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.
What is the polynomial-time reduction of problem 1 to problem 2?

Let TSP1 denote the following problem: given a TSP instance in which all edge costs are positive integers, compute the value of an optimal TSP tour. Let TSP2 denote: given a TSP instance in which all edge costs are positive integers, and a positive integer T, decide whether or not there is a TSP tour with total length at most T. Let HAM1 denote: given an undirected graph, either return the edges of a Hamiltonian cycle (a cycle that visits every vertex exactly once), or correctly decide that the graph has no such cycle. Let HAM2 denote: given an undirected graph, decide whether or not the graph contains at least one Hamiltonian cycle.
From Roughgarden's online algorithms course

The solution:

If TSP2 is polynomial-time solvable, then so is TSP1. If HAM2 is polynomial-time solvable, then so is HAM1.

First the reduction from P2 to P1 is easy cause if you can decide whether there is one cycle you can also decide whether there is at least one cycle. The other way around is more tricky.
Notice that P1 can be solved in polynomial time if we have an oracle for P2 (an oracle for P2 means that we can use a subroutine that solves P2).
algorithm for P1 with input G = (V,E):
  E' = {} # edges of "Hamilton Cycle"
  run subroutine for P2 on G
  if there is no Ham. Cycle:
    report that there is no Ham. Cycle
  for e in E:
    run P2 on (V,E - {e})
    if (V,E - {e}) contains "Hamilton Cycle":
      E <- E - {e}   # remove e
    else:
      E' <- E' + {e} # add e to cycle
  return E'

It uses the procedure for P2 $O(|E|)$ times, thus we obtained a polynomial reduction.


Proof technique in complexity theory I have a (stupid ?) question about complexity theory. It's about a "proof technique".

I want to compare 2 models of computation. I want to prove that for each langage recognized in polynomial time by a machine of the first model, there exists a machine of the second class that recognizes the same langage in polynomial time. Can I use this argument in my proof :

  Let M be a machine of the first class that recognizes a langage L in time T(n) (where T is a polynomial, and n the size of the input word). Let N be a machine of the second class that is able to computes T(n) ...

The idea is to use the knowledge of T(n) to have a bound on the space used on each input by the machine of the first class, which that makes the construction of the machine of the second class easier. However, it seems a bit strange to say that we explicitly know T(n)... Is it allowed ?

You can indeed assume that you know a polynomial bound on the time it takes to compute a polytime function. This is an example of a non-constructive argument.

The down side is that you won't be able to construct a computable function transforming polytime function of one model to the other. In some situations (say a diagonal argument) this is needed, and then the trick is to assume that programs are clocked, i.e. come with their own time bounds. This makes sense in that application since we can enumerate all polytime functions as computed by polynomially clocked machines. In your case, however, you don't need to worry about such issues.


Shortest path between two points with n hops Is there an efficient algorithm which computes the (possibly approximately) shortest $n$-edge path between two points $A$ and $B$ in a weighted complete graph? Dijkstra won't work because it will just give the trivial answer of $A\to B$. I'd like to find an $n$-edge path (e.g. for $n=4$, find $C$, $D$ and $E$ which minimize total path length of $A\to C\to D\to E\to B$).

If vertices can be visited more than once, then yes: you can create $n+1$
copies of the graph, with each vertex $v$ in the original graph becoming the $n+1$ vertices $v_1, \dots, v_{n+1}$ and each edge $uv$ in the original graph becoming the set of edges $u_iv_{i+1}$ for all $1 \le i \le n$; now run Dijkstra on the resulting graph with start vertex $A_1$ and end vertex $B_{n+1}$.  Intuitively, each edge traversed in any path necessarily takes you to the next "level" of the graph.

If vertices cannot be visited more than once, then there's no known poly-time algorithm, since setting setting $n$ to one less than the number of vertices would solve the NP-hard Hamiltonian Path problem.  (Although the HP problem technically asks for any path that visits all vertices exactly once, a poly-time algorithm for the simple-paths version of your problem would nevertheless give you a poly-time algorithm for HP: just run it $O(n^2)$ times, one for each possible pair of start and end vertices.)


Show that the language of words with even sum of positions of a letter is regular Let $\Sigma=\{a,b\}$, and let $S(a)$ be sum of the positions of $a$ of string $S$. I want to prove $$L=\{S\in \Sigma^{*} \mid S(a)=0(\bmod 2)\}$$ is regular.

What I was thinking is to do somehow keep track of sum of positions of $a (\bmod 2)$ For that I was thinking to do like take set of states as $\{0,1\}\times \{0,1\} \times \{0,1\}$. And starting state $\{0,0,0\}$. My aim to is to keep track sum of positions of $a$ at first component. So starting from initial state, if it read consecutive $x,b$s then it will go to $(0,0,x(\bmod 2))$ then after reading $y,a$s it goes to $(xy+y(y+1)/2(\bmod 2),y(\bmod 2),x(\bmod 2)$ after reading $z,b$s it goes to $(xy+y(y+1)/2 \bmod 2),y(\bmod 2),(x+y)z+(x+y)(x+y)/2(\bmod 2)$ ... and so on. And set accepting state ${0}\times {0,1}\times {0,1}$. I believe its working but I don't understand how to define on each state.

If the sum of positions at which $a$s occur is even, that just means that there are an even number of $a$s in odd positions. It's straightforward to design an automaton to accept this criterion: it's a minor variant of requiring an odd number of $a$s.


Does immutability in functional programming really exist? Although I work as a programmer in my daily life and use all the trendy languages (Python, Java, C, etc) I still have no clear view of what functional programming is. From what I've read, one property of functionally languages is that data structures are immutable. For me this alone raises a lot of questions. But first I will write a bit of what I understand of immutability and if I'm wrong, feel free to correct me.

My understanding of immutability:

When a program starts it has fixed data structures with fixed data
One can't add new data to these structures
There are no variables in the code
You can merely "copy" from the already data or currently calculated data
Because of all above, immutability adds huge space complexity to a program

My questions:

If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?
What is the point in having a program that can't get new data? Say you have a sensor attached to your computer that wants to feed data to the program. Would that mean that we can't store the incoming data anywhere?
How is functional programming good for machine learning in that case? Since machine learning builds from the assumption of updating the program's "perception" of things - thus storing new data.

When a program starts it has fixed data structures with fixed data

This is a bit of a misconception. It has a fixed form and a fixed set of rewrite rules but these rewrite rules can explode into something much larger. For instance the expression [1..100000000] in Haskell is represented by a very small amount of code but its normal form is massive.

  One can't add new data to these structures

Yes and no. The purely functional subset of a language like Haskell or ML can't get data from the outside world but any language for practical programming has a mechanism for inserting data from the outside world into the purely functional subset. In Haskell this is done very carefully but in ML you can do this whenever you want.

  There are no variables in the code

This is pretty much true but don't confuse this with the idea that nothing can be named. You name useful expressions all the time and constantly reuse them. Also both ML and Haskell, every Lisp I have tried, and hybrids like Scala, all have a means of creating variables. They just are not commonly used. And again the purely functional subsets of such languages don't have them.

  You can merely "copy" from the already data or currently calculated
  data

You can perform calculation by reduction to normal form. The best thing to do is probably to go write programs in a functional language to see how they do in fact perform calculations.

For instance "sum [1..1000]" is not a calculation I want to perform but it is quite handily done by Haskell. We gave it a small expression that had meaning to us and Haskell gave us out the corresponding number. So it definitely performs calculation.

  If data structures are supposed to remain as they are (immutable), how the hell does someone add a new item in a list?

You don't add a new item to a list, you create a new list out of the old one. Because the old one can't be mutated it is perfectly safe to use it in the new list, or whereever else you want. Much more data can be safely shared in this schema.

  What is the point in having a program that can't get new data? Say you
  have a sensor attached to your computer that wants to feed data to the
  program. Would that mean that we can't store the incoming data
  anywhere?

As far as user input goes, any practical programming language has a way of getting user input. This happens. However there is a fully functional subset of these languages that you write most of your code in and you reap the advantages in this way.

  How is functional programming good for machine learning in that case?
  Since machine learning builds from the assumption of updating the
  program's "perception" of things - thus storing new data.

This would be the case for active learning but most machine learning I have worked with (I work as a code monkey in a machine learning group and have done so for a few years) has a one time learning process where all the training data is loaded in at once. But for active learning you can't do things 100% purely functionally. You are going to have to read in some data from the outside world.


Is implication(function) more fundamental than lets say conjunction(product) in type theory? According to the answer at (How to define function type in AGDA) the function type is kind of a fundamental thing in Agda and needed for bootstrapping, hence end user can not define it like what they do for conjunction(product) type and has to be predefined at the language level. Does this mean that implication(function) type is more fundamental than types like product(conjunction) since function is used in defining those types?

For Agda, I think, as stated in the other question, that the fact that function types (or rather Π-types) are built-in while pairs (or even Σ-types) aren't so much is a reasonable argument that they are more fundamental in Agda. That said, even there it's not completely clear cut. For example, Σ-types/pairs are introduced in Agda via inductive data type declarations which are largely unrelated to Π-types. On the other hand, you could Church-encode pairs in terms of Π-types but to actually push this all the way through you'd need universes (which Agda does have) so it's not Π-types alone that do it.

I find comparing "how fundamental" things are very ambiguous and usually not useful. Something being "more fundamental" means it's "closer" to some foundations (fundament). In the context of a specific foundational system, e.g. Agda, that can be reasonably clear, but in general things that are fundamental in one foundation may be derived in another. More generically, "fundamental" has connotations that can easily pull in opposite directions. On the one hand, if I can derive $X$ from $Y$ but not vice versa, it would seem $Y$ is "more fundamental" in some sense. On the other hand, "fundamental" has connotations of simplicity, minimality, and a kind of unavoidability. If given all of $X$, $Y$, and $Z$ I can derive $W$, but given just $W$ I could derive each of $X$, $Y$, and $Z$, is $W$ more fundamental or less fundamental than $X$? Maybe $W$ is just a complex composite of $X$, $Y$, and $Z$. Because $X$ is derivable from $W$, that means $X$ is a more omnipresent concept; $X$ can exist even if $W$ does not but not vice versa.

At any rate, let's move to some more technical goodness that talks about how pairs and functions relate without trying to rank them. Unsurprisingly, category theory provides a good vantage point for gaining insight on these types of questions, though it is important to compare what the category theory suggests to what the type theorists actually do because these don't always line up. It can be quite interesting on both sides to see what is needed to make them line up.

Arguably the simplest example is cartesian closed categories. A cartesian category is one that has finite products, this means (the existence of terminal objects and) $\text{Hom}(A,B)\times\text{Hom}(A,C)\cong\text{Hom}(A,B\times C)$ (natural in $A$, $B$, and $C$). This is a characterization of binary products. A cartesian closed category additionally has $\text{Hom}(A\times B,C)\cong\text{Hom}(A,C^B)$ characterizing exponents in terms of products. This is to say a (parameterized) adjunction $-\times B\dashv (-)^B$. Hagino's Categorical Programming Language (CPL) described in his thesis allows declaring the function type constructor just this way (see sections 3.3.2 and 3.3.3). The type theoretic view of this is the simply typed lambda calculus (STLC) with products. But the STLC is usually not presented with products, or at the very least they are optional. So how are function types described in STLC without products? Usually by the following two rules (or some variation on them):$$\cfrac{\Gamma, x\!:\!A\vdash M:B}{\Gamma\vdash(\lambda x\!:\!A.M) : A\to B}\to\!\!I\qquad\cfrac{\Gamma\vdash M : A\to B\qquad \Gamma\vdash N:A}{\Gamma\vdash (M\,N) : B}\to\!\!E$$ This characterizes function types without any reference to product types. This is typical in modern type theory; type constructions are characterized without referencing other type constructions so that you can build type theories a la carte. In tihs sense, product types and function types are somewhat orthogonal.

Why does the categorical approach need products? Roughly speaking, an arrow $t\in\text{Hom}(A,B)$ corresponds to a term $x\!:\!A\vdash t:B$. So the issue is simply that we need some way of talking about arrows with more than one input. Products are one way, but an alternative, more direct approach would be to use (cartesian) multicategories. However, a more common approach is to split the adjunction characterizing function types in terms of product types into two adjunctions. Instead of having $-\times B\dashv (-)^B$ as described earlier, we can split this into $\Sigma_B\dashv p^*\dashv \Pi_B$ where $p : [\Gamma,B]\to [\Gamma]$ and $p^* : \mathcal{E}_\Gamma\to\mathcal{E}_{\Gamma,B}$. Here $\mathcal{E}_\Gamma$ can be thought of as a category of terms in context $\Gamma$. The machinery to do this is indexed or mostly equivalently fibered categories. $p^*$ is called a weakening functor and it corresponds to adding an unused variable (of type $B$) to the context. Now we can consider indexed-/fibered-categories where only one or the other (or neither or both) of those adjunctions hold. A simpler but less general approach to this is to use polycategories as Hasegawa does in Decomposing typed lambda calculus into a couple of categorical programming languages. A polycategory, $\mathcal{C}[x:B]$, is a category, $\mathcal{C}$, that has a terminal object and to which an arrow $x : 1 \to B$ is freely added. We of course have an inclusion of $\mathcal{C}$ into $\mathcal{C}[x:B]$, and this inclusion takes the place of $p^*$. When this perspective is related back to type theory, we end up splitting the lambda calculus into the kappa calculus and the zeta calculus. The kappa calculus captures a first-order notion of multi-parameter functions. The zeta calculus captures the higher-order aspect of the lambda calculus, but the result is quite strange and awkward. Either way, these approaches place product types and function types on somewhat even ground.


Solving SAT using tableau calculus I've learned about tableau calculus which is a decision procedure solving the problem of satisfiability of a first order logic formula.
Now I'm wondering why this technique can't be used to solve the satisfiability problem (SAT)?

It can be, but the solution process is equivalent to converting a CNF formula to DNF, which is NP-hard.  You will at worst end up exploring an exponential number of disjunction branches.


Why do heuristic functions only approximate the real value of the cost? As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?

If you create a heuristic that returns the exact cost for each node in the search tree, you can find the optimal solution easily: Start at the initial state and generate all successor states. Take the state with the best heuristic value and repeat, until you find the goal state. Because the estimated cost (from the heuristic) for each node in the search tree is equal to the actual cost, you never make a wrong decision.

Unfortunately for most problems constructing such a heuristic would mean that for each node to evaluate you calculate the solution and then return the cost of the solution. Thus you already solve your problem inside the heuristic function.


How does knowing the input size make the time complexity of a function constant? After reading the question and answers on Time complexity of min() and max()? I would like to clear up some confusion on the relation between time complexity and size of input.
First, I've noticed most of the time people omit what exactly n represents in big O notation. Usually it's related to the input, but it may be the value or length in bits or something else. Am I right that it's usually inferred from context?
When is a function O(1) vs O(n)? I had thought that only functions that do not depend on the input would be O(1) for example
foo()
{
  return "bar"
}

Or accessing certain data structures like an array arr[0] or a map would have operations of O(1). But in the linked question some answers stated this is only true if the size is known. What difference does this make? Even if the size is known, some operations may take O(n). For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed. So why do some people say knowing the size makes it constant time?

First, I've noticed most of the time people omit what exactly n represents in big O notation.

Yes, that is indeed a bad habit. In general, when you analyze complexity, you must specify:

Are you talking about space complexity, step complexity, time complexity?
Are you talking about best-case, worst-case, amortized worst-case, average case, expected case?
What is your machine model? (I.e. what operations exist?)
What is your cost model? (How long do those operations take?)
What are you actually counting? (Comparisons, stores, loads, arithmetic operations, bit operations, etc.)
How do you define "length of the input"? (Number of elements, number of bits, etc.)
What is the distribution of your inputs? (In case of average or expected complexity.)

Usually it's related to the input, but it may be the value or length in bits or something else.

For data structures, it is usually the number of elements. For strings, it already gets trickier: is it the number of bytes, number of octets, number of `chars, number of code points, number of characters, number of graphemes, number of grapheme clusters?
One thing that catches many people out is that for numbers, it is usually not the magnitude, it is the length (i.e. the number of "digits" or bits), which is the logarithm of the magnitude.

Am I right that it's usually inferred from context?

Indeed. However, as mentioned above, for numbers, it is often inferred wrong.
The reason why we usually use the length of numbers is that arithmetic operations depend on the number of digits, not on the magnitude of the number: adding 1+1 take the same time as adding 4+4, but adding 10+10 takes twice as long. Adding 4999+5000 doesn't take 5000 times as long as adding 1+1, it only takes 4 times as long.

For example given in an array of 100 elements you know the value 50 appears and would like to find its index. That would be O(n) because the array would have to be traversed.

No, it would not. O(1) means the number of comparisons (which is what we are usually counting when talking about "searching") is bounded by a constant. In your example, you will never need more than 100 comparisons, therefore the number of comparisons is bounded by 100, which is a constant.
Therefore, the time complexity is O(100), which is the same as O(1).


Maximum coverage 1/2-approximation algorithm: why does the central lemma hold? I am looking for an approximation algorithm for the Maximum Coverage problem and a proof of its approximation ratio. As approximation algorithm I use the greedy algorithm which chooses the set that maximizes the number of new elements at each turn (same as the one proposed in the Wikipedia article). However it is not as trivial to reach a result about the approximation ratio of this greedy approach.

So I did some research and found these lecture notes that describe some useful concepts for this problem and also proves a lemma. Now let me iterate what is said in these lecture notes before we get to the lemma.

Maximum Coverage problem
Given a set of sets $U=\{S_{1},\dots,S_{m}\}$ and a number $k$, choose (at most) $k$ sets such that the union of the sets is maximized, or $\max_{I\subseteq U}\vert \cup_{j\in I}S_{j}\vert$ for some index set $I$. The sets may have elements in common. Let $\mathbf{OPT}$ denote the optimal solution, i.e. numbers at most covered by $k$ sets, let $a_{i}$ denote the number of newly covered elements in the $i$:th iteration by the greedy algorithm, let $b_{i}$ be the total number of covered elements in the $i$:th iteration, i.e. $b_{i}=\sum_{j=1}^{i}a_{i}$, and let $c_{i}$ be the number of uncovered elements at the $i$:th iteration, i.e. $c_{i}=\mathbf{OPT}-b_{i}$. Moreover, $a_{0}=0$, $b_{0}=0$ and $c_{0}=\mathbf{OPT}$.

Lemma: The number of newly covered elements at the $(i+1)$:th iteration (i.e. $a_{i+1}$) is always greater than or equal to $(1/k)\cdot$number of uncovered elements at the $i$:th iteration, or $a_{i+1}\geq c_{i}/k$.

Proof: Optimal solution covers $\mathbf{OPT}$ elements at $k$ iterations. That means, at each iteration there should be some sets in $U$ whose size is greater than or equal to the $(1/k)$ of the remaining uncovered elements, i.e., $c_{i}/k$. Otherwise, it was impossible to cover $\mathbf{OPT}$ many elements at $k$ steps by the optimal solution. Since the approximation algorithm is greedy, i.e., choosing always the set covering maximum number of uncovered elements,the chosen set at each iteration should be at least the $(1/k)$ of the remaining uncovered elements. That is, $a_{i+1}\geq c_{i}/k$.

I do not understand this proof, why does it have to be the case there exist such sets? And why is the size of the set important, is it not the number of new elements the set contributes that is important? It all seems arbitrary to me to choose that there is a lower bound of $(1/k)\cdot c_{i}$ for $a_{i+1}$. I am also confused about how the optimal solution is related to the greedy solution, what is the rationale behind the statement that if this is not true then it would have been impossible for the optimal solution to be $\mathbf{OPT}$ in $k$ iterations? Since I have trouble understanding at all, is there any other way to explain this lemma?

Let $S_{O_1},\ldots,S_{O_k}$ be an optimal solution, and let $O = S_{O_1} \cup \cdots \cup S_{O_k}$.

At the $i$'th iteration, suppose that the elements covered by the sets chosen the algorithm form the set $T$. Let $S'_{O_i} = S_{O_i} \setminus T$ and $O' = O \setminus T$, that is, we have removed from the optimal solution all elements already covered. Since
$$
|O'| = |S'_{O_1} \cup \cdots \cup S'_{O_k}| \leq |S'_{O_1}| + \cdots + |S'_{O_k}| \leq k \max_{i=1}^k |S'_{O_i}|,
$$
we see that among the sets $S_{O_1},\ldots,S_{O_k}$, at least one (the one maximizing $\max_i |S'_{O_i}|$ covers at least $|O'|/k$ uncovered elements.

The greedy algorithm chooses a set covering at least as many uncovered elements. This allows us to obtain a lower bound on its approximation ratio, as follows. Let $T_i$ be the union of the sets chosen in the first $i$ steps of the greedy algorithm. The starting point is $T_0 = \emptyset$. At step $i$, the argument above shows that we cover at least $|O'|/k$ new elements. Since $|O'| = |O \setminus T_{i-1}| \geq |O| - |T_{i-1}|$, this shows that
$$
|T_i| \geq |T_{i-1}| + (|O| - |T_{i-1}|)/k = \left(1 - \frac{1}{k}\right) |T_{i-1}| + \frac{|O|}{k}.
$$
In particular,
$$
\begin{align}
&|T_1| \geq \frac{|O|}{k} \\
&|T_2| \geq \frac{|O|}{k} + \left(1 - \frac{1}{k}\right) \frac{|O|}{k} \\
&|T_3| \geq \frac{|O|}{k} + \left(1 - \frac{1}{k}\right) \frac{|O|}{k} + \left(1 - \frac{1}{k}\right)^2 \frac{|O|}{k}
\end{align}
$$
and so on. At the end of the algorithm we get a set $T_k$ satisfying
$$
\begin{align}
|T_k| &\geq \frac{|O|}{k} \left[1 + \left(1 - \frac{1}{k}\right) + \cdots + \left(1 - \frac{1}{k}\right)^{k-1}\right] \\ &=
\frac{|O|}{k} \frac{1 - \left(1 - \frac{1}{k}\right)^k}{1 - \left(1 - \frac{1}{k}\right)} \\ &=
\left(1 - \left(1 - \frac{1}{k}\right)^k\right) |O|.
\end{align}
$$
Now it's time for some calculus:
$$
\ln \left(1 - \frac{1}{k}\right) = - \frac{1}{k} - \frac{1}{2k^2} - \cdots \leq -\frac{1}{k},
$$
and so
$$
\left(1 - \frac{1}{k}\right)^k = \exp\left[k\ln \left(1 - \frac{1}{k}\right)\right] \leq \exp (-1) = 1/e,
$$
implying that
$$
|T_k| \geq \left(1 - \frac{1}{e}\right) |O|.
$$
In other words, the greedy algorithm gives a $(1-1/e)$-approximation (this is better than your claimed $1/2$). It turns out that $1-1/e$ is tight for the greedy algorithm, and moreover, then $1-1/e$ cannot be improved by a polynomial time algorithm unless $\mathsf{P} = \mathsf{NP}$ (and unconditionally in the value oracle model).


Prove that a $k$-regular bipartite graph with $k \geq 2$ has no cut-edge Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.

Explanation of the terms:

$k$-regular means that all vertices have degree $k$;
bipartite means that there are 2 sets of vertices $X, Y$, where vertices from $X$ only have edges with vertices $Y$ and vertices from $Y$ only have edges with vertices from $X$;
cut-edge is an edge which removal disconnects the graph;

This is b) part of the exercise, maybe a) part can help:

a) If all vertices $v \in G$ have an even degree, $G$ does not have cut-edge

From a) it actually follows that for even $k$, b) is true, thus only case with odd $k$ left to prove.

Ok, here is a simple proof I came up by myself. I was apparently going the wrong way in trying to prove the exercise.

Proof. Suppose edge $e$ is a cut-edge. Study graph $G-e$. For any $v \in G-e$ other then $e$ endpoints $x, y$, the vertex degree $d(v) = k$, and $d(x)=d(y)=k-1$.

Now, since graph $G$ is bipartite, graph $G-e$ remains bipartite. Also, because $e$ is a cut-edge, $G-e$ is composed of 2 components $H_1, H_2$, which are also both bipartite, and each contains exactly one of $x, y$. Assume WLG that $H_1$ has vertex $x$, that $H_1$ has vertex bipartition $X_1, Y_1$ and that $x \in X_1$.

Clearly, in subgraph $H_1$, we have

$S_1 = \sum_{v\in X_1 }d(v) = k(|X_1|-1) + k-1$ and $S_2 = \sum_{v\in Y_1 }d(v) = k(|Y_1|)$, and $S_1$ can't be equal $S_2$ unless $k=1$. However, it must be the case that $S_1 = S_2$ in a bipartite graph. Thus, our initial assumption that $e$ is a cut-edge was wrong. Therefore, $G$ has no cut-edge. $\Box$


Proving correctness of a loop that calculates the sum of array I am trying to mathematically prove that the following program is correct:

int ArraySumC(int[] a) {
    int i = 0;
    int j = 0;

    while (i <= n) {
        j = j + a[i];
        i = i + 1;
    }

    return j;
}

When the loop ends, we want the invariant, Q, and the condition for loop termination, B'.

Q ∧ B' = Q ∧ i > n

We also want the post condition

j = sum(a[1] ... a[n])

I'm not sure how to go from here, because I don't know what Q should be. I am used to B' being an equality and thus being able to substitute one side of B' into the post condition. Should I assume that B' is i = n + 1? Or is there another way to deal with the inequality?

I think your postcondition is wrong. Since index i is initialized at 0, you're actually summing from 0 to n, not from 1 to n. The postcondition, lets call it $P$, should be:

$$ j = \sum_{k=0}^{n} a[k] $$

Or:

j = sum(a[0] ... a[n])

Usually you would write $B$ as $i \neq n+1$ instead of $i \le n$, because it makes the proof easier. In that case, you would choose $Q$ as (assuming array indexing starts at 0):

$$ j = \sum_{k=0}^{i-1} a[k] $$

Or in your notation:

j = sum(a[0] ... a[i-1])

Then $ Q \land \lnot B \implies P$ is true because you can substitute $i$ by $n+1$. Of course, you would have to prove that $Q$ is a valid invariant, but I'll leave that to you.

In your case,$\lnot B$ is $i>n$ instead of $i = n + 1$, so you can't use substitution. You can deal with the inequality by adding information to the invariant and then proving $i = n +1$ using this new information. Our new invariant $Q'$ could be:

$$Q \land i \le n+1$$

This new condition holds before the loop starts because $i$ starts at 0 and $n+1$ must be at least $1$.To prove that $Q'$ is a valid invariant, we have to show that it also holds after every iteration. Each time the loop executes $i$ changes to $i+1$, so we must prove that $ i+1 \le n+1$, which is true because the loop condition states that $i \le n$ was true when the iteration started.

Now we know that $Q \land i \le n + 1 \land i > n$ holds after the loop ends. And since $i \le n + 1 \land i > n \implies i = n + 1$ and $Q \land i = n + 1 \implies P$, the program is correct.


Why is $((aa)^*bb(aa)^*bb(aa)^*)^*$ of star-height 1 A generalized regular expression is like a regular expression but with one more operation allowed: complementation. The (generalized) star-height of a generalized regular expression is the maximal number of nested Kleene stars. The star-height of a language is the minimal star-height of a regular expression describing it. It is not known if there is even a language of star-height 2.
So I imagine the langage $((aa)^*bb(aa)^*bb(aa)^*)^*(aa)^*$ of words consisting of concatenations of $aa$ and $bb$, with an even number of $bb$, is of generalized star-height $1$. But I couldn't prove it. In the paper Some results on the generalized star-height problem (Pin, Straubing, Thérien), lemma 6.1 (the transfer lemma) cannot be applied because both $(bb)^*$ and $(aa)^*$ are of star-height 1.
I saw elsewhere some languages which were conjectured to be of star-height 2 and they were more complex than the one I give, so it is very probably of star-height 1. Is it the case?

(This is an attempt to an answer, I hope the details are right.)
Your language consists of all strings in $(aa+bb)^*$ with an even number of $bb$.
We are allowed to use complementation, so we start by looking at the complement of the language. I think we can split the complement into two (overlapping) parts

strings not of the form $(aa+bb)^*$, that language has starheight one.
strings of the form $w_0\cdot bb\cdot w_1\cdot bb\cdot w_2 \dots bb\cdot w_n$, where (1) the number of $bb$ is odd, and (2) the $w_i$ do not contain any $bb$ (but I will have to be more precise on that)

Now we will try to find an expression for the language $W$ of the $w_i$ without using star. That means we can use the star to count the odd number of $bb$, as in $(W\cdot bb\cdot W\cdot bb)^*\cdot W\cdot bb\cdot W$.
This is the tricky part. Strings from $W$ are either

the empty string $\varepsilon$
just one single $a$
of the form $axa$, where $a$ does not contain $bb$. Not "containing $bb$" is the complement of $(a+b)^*bb(a+b)^*$, and as you know $(a+b)^*$ is again star-free.

The strings we now have specified can have longer stretches of $b$'s, but whenever that happens the $b$'s come in pairs.


Does a Universal Turing Machine have more computational power than a non-universal one? I'm a bit confused about these concepts. As far as I understand, something is Turing complete when it can simulate a Turing machine. And there is this thing called a Universal Turing machine which is universal because it can simulate a Turing machine. Which to me, implies there are Turing machines that are not universal and cannot simulate a Turing machine. Does this mean non-universal Turing machines are not Turing complete?

Could anyone clarify this concepts for me?

In short yes, a non-universal Turing Machine is not Turing-complete.

The key part is that a computational model is Turing-complete if it can simulate any Turing Machine (or using the transitivity of the simulations, if it can simulate a Universal Turing Machine).

As you note, many Turing Machines are not Universal, they compute something, but they can't simulate any computation that any Turing Machine could do.

A possibly intuitive practical way of thinking about this is that Turing Machines are normally equivalent to programs - they take a particular type of input and compute some output. Universal Turing Machines are equivalent to programming languages or computers - you can build/run any program/Turing Machine on them. Of course I'm using "equivalent" very loosely here.


Distinction between statements, declarations, and expressions in formal grammar I am learning basic grammar and parsing concepts and ran into this statement:

  Nonterminal symbols represent syntactic entities: statements, declarations, or expressions.

But the three terms (statements, declarations, expressions) were not really defined. I have plenty of programming experience so I have a fairly intuitive grasp of the terms, but I'm wondering, from a language grammar standpoint, what are the generally accepted definitions for each? When I searched online I found several language-specific discussions but nothing that gave a general definition of these terms that can apply across any language.

Are there such definitions out there? Thanks.

These are informal terms. For example, in the C language:

Statements are things like x = 3;.
Declarations are things like int x;.
Expressions are things like x * y.

So declarations are a particular type of statements, and expressions appear in statements.

A better formulation of the statement you quoted would be:

  Nonterminal symbols represent syntactic entities such as statements, declarations, or expressions.


How to know maximum final states in a DFA? If a NFA contains N states, then Equivalent DFA can have atmost $2^N$ states.

Is there any method or any concept to know, how many final and non-final states will be there in the equivalent DFA ?

Take for example : An NFA has 7 states out of which 3 are final states. Its equivalent DFA can have atmost 128 states.

Then is there any method to find maximum number of final states and non final states in converted equivalent DFA ?

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

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

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


Why does this greedy algorithm fail to accurately determine whether a graph is a perfect matching? I came across this problem in Tim Roughgarden's course on Coursera:

  In this problem you are given as input a graph $T=(V,E)$ that is a
  tree (that is, $T$ is undirected, connected, and acyclic). A perfect
  matching of $T$ is a subset $F \subseteq E$ of edges such that every
  vertex $v \in V$ is the endpoint of exactly one edge of $F$.
  Equivalently, $F$ matches each vertex of $T$ with exactly one other
  vertex of $T$. For example, a path graph has a perfect matching if and
  only if it has an even number of vertices.

  Consider the following two algorithms that attempt to decide whether
  or not a given tree has a perfect matching. The degree of a vertex in
  a graph is the number of edges incident to it. (The two algorithms
  differ only in the choice of $v$ in line 5.)

Algorithm A:

While T has at least one vertex:
  If T has no edges:
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with maximum degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

Algorithm B:

While T has at least one vertex:
  If T has no edges:
    halt and output "T has no perfect matching."
  Else:
    Let v be a vertex of T with minimum non-zero degree.
    Choose an arbitrary edge e incident to v.
    Delete e and its two endpoints from T.
[end of while loop]
Halt and output "T has a perfect matching."

Now, the answer key says:

  Algorithm $A$ can fail, for example, on a three-hop path. Correctness of
  algorithm $B$ can be proved by induction on the number of vertices in $T$.
  Note that the tree property is used to argue that there must be a
  vertex with degree $1$; if there is a perfect matching, it must include
  the edge incident to this vertex.

However, I think I found a counter-example which shows that Algorithm B may not be correct. Am I missing something?  Consider the following graph (say $T$):

If we follow B:

Step 1: Let $v=3$ (all vertices have the same degree) and $e=(2,3)$. Remove $e$ along with vertices $3$ and $2$.

Step 2: Let $v=1$ and $e=(0,1)$. Remove $e$ along with vertices $0$ and $1$.

Step 3: No vertices are left. Hence we get the output: "T has a perfect matching."

But clearly, our original graph was not a perfect matching as all the nodes were of degree $3$.

Note: I assumed that ties are meant to be broken arbitrarily by the algorithm.

"Consider the following two algorithms that attempt to decide whether or not a given tree has a perfect matching". Your graph is NOT a tree as it has a cycle $0, 1, 2, 0$.

Furthermore, your graph does have a perfect matching. In fact, the edges $(2,3)$ and $(0,1)$ obtained by your step 1, 2 and 3 is a perfect matching. And hence, it is not true that "our original graph was not a perfect matching as all the nodes were of degree 3". Plenty of graphs whose nodes are all of degree 3 have a perfect matching.


Why do researchers only count the number of multiplications when analyse the time complexity of Matrix Multiplication? In this article about the recent breakthough in Matrix Multiplication, it quotes Chris Umans's words:

Multiplications are everything. The exponent on the eventual running time is fully dependent only on the number of multiplications. The additions sort of disappear.

I was wondering how I should understand this. Why the number of additions doesn't matter?

It looks like the article was written by someone who does not understand matrix multiplication.

the number of additions is equal to the number of entries in the matrix, so four for the two-by-two matrices and 16 for the four-by-four matrices.

With the classic matrix multiplication algorithm (which is the one explained in the example) between two $4\times 4$ matrices, each coefficient of the product requires $3$ additions, so a total of $3\times 16 = 48$ additions, not $16$.
Usually, when it is said that only multiplications matter and not additions, it means of matrices, not coefficients.
For example, a "naive" divide-and-conquer strategy compute $A\times B$ where $A,B$ are matrices of size $n\times n$ by doing $8$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ (and some additions of matrices, but those are done in complexity $O(n^2)$, which is negligible in front of the complexity of matrix multiplication). That way, the complexity verifies $C(n) = 8C\left(\frac{n}{2}\right) + O(n^2)$ and it is easily proven that $C(n) = O(n^3)$, so this strategy is not an improvement.
The Strassen algorithm use a divide-and-conquer strategy to improve complexity: it does $7$ products of matrices of size $\frac{n}{2}\times\frac{n}{2}$ and some additions, so the complexity verifies $C(n) = 7C\left(\frac{n}{2}\right) + O(n^2)$ and we get $C(n)\simeq O(n^{2.8})$.
In the two examples above, the number of matrices multiplications matter much more than the number of matrices additions. But in both, the number of multiplications/additions on coefficients is not compared.
It is confirmed in the article:

Volker Strassen reportedly set out to prove that there was no way to multiply two-by-two matrices using fewer than eight multiplications. Apparently he couldn’t find the proof, and after a while he realized why: There’s actually a way to do it with seven!


How does the OS detect B&B violation from hardware? After reading about Base & Bounds memory protection mechanism from Stanford CS140 lecture notes, I understood from the explanation below that there is an integrated circuit performing B&B checks somewhere in the CPU (correct me if I'm wrong):

On each memory reference, virtual address is compared to the bound
register, then added to the base register to produce a physical
address. A bound violation results in a trap to the operating system.

However I didn't find any information about how the OS detects such violation from the hardware in order to handle the exception.
Does anyone have any idea?

When an invalid access is detected, the #BR exception is triggered, the CPU will switch to privilege mode and load the corresponding vector (Bounds range exceeded) from the IVT. The CPU also pushes the faulty EIP (as well as other things) to the kernel stack and updates the BNDSTATUS register to describe the fault.

Note: the #BR exception saves other purposes as well because Base & Bound works like paging: there is a 2-level hierarchy to store B&B values (since the CPU can only store 4 of them in registers), so it works a bit like a TLB but for B&B.


Maximum weight sum in a subgraph Let $G = (V, E, W)$ be a weighted graph with positive and negative weights. I would like to find the set of vertices $V^\prime$ such that the sum of the weights of the edges that they share is the maximum you can get from $G$. I suspect that this is an NP-complete problem, so my question is whether this can be reduced to a known NP-complete problem. Since $V^\prime$ does not necessarily have to be the minimum subset that satisfies the constraint, I think I can't use the solutions for the vertex/set cover problems, so any ideas would be welcome.

An easier problem to use would be max clique. We do the transformation as follows. We take the graph that we wish to find the max clique in and give all edges in it weight 1, and for all non edges we give weight (-)infinity (or if you dont like infinity an arbitrarily large number based on the number of edges total, negative enough so that if one is picked the total will always be negative). This problems solution will give us a clique since the negative infinity weight will prevent selecting anything that does not have edges between them for the solution. This clique is also the largest, as a larger clique would have a larger edge sum and we assume this algorithm returned the largest edge sum. This is therefor at least as hard as solving max clique, which is NP complete.


Is it possible to calculate the propagation delay if only the length of the link is known & not the speed at which a bit travels into the link? Consider a $10^7$ bps link that is $400$ km long, with a queue large
  enough to hold $2000$ packets.Assume that the packets arrive at the
  queue with an average rate of $4000$ packets per second and that the
  average packet length is $2000$ bits.Find the average number of
  packets in the queue.

I am getting Average Queue length = 0.

In this question is it possible to calculate Propagation delay?
How can we calculate the propagation delay until we don't know about the speed at which a bit travels in the link?

I believe your approach is right. Since we don't have any other information given. Then this means the packets are getting consumed at the rate same as link bandwidth. So Avg packet waiting must be 0.


Is deciding whether or not a graph is bipartite in $L$? Let's consider the problem:

  Prove that decision whether a graph is bipartite is in $LOGSPACE$.

I am convinced that I should use Reingold's theorem. I know that I test whether graph contains an odd-length cycle.

For a given graph $G = (V,E)$ I can define the graph $$G' = (V', E') \\ V' = \{ v^1, v^2 | v \in V \} \\ E' = \{(u^1, w^2), (u^2, w^1) | (u,w) \in E\}$$

And now, the vertex $v$ resides in odd-length cycle iff there is a path between $v^1$ and $v^2$.

But, how can I construct $G'$ using $LOG$ memory?

Your construction shows that checking whether an undirected graph is bipartite is logspace reducible to PATH (deciding whether there exists a path between two vertices in an undirected graph).

Recall that if $A$ is logspace reducible to $B$ and $B\in L$, then $A\in L$. To decide $A$ in logspace, you don't actually compute the reduction (as its output can be of polynomial length), but compute a single bit of the reduction whenever it is requested. More concretely, suppose $f$ is a logspace reduction from $A$ to $B$. To decide $A$, given input $x$, execute the logspace machine for $B$ and keep a counter $i$ for the location on its input tape. Whenever $B$ wants to read a symbol from its input, compute the $i$'th bit of $f(x)$, which requires only logarithmic space (as $f$ is a logspace reduction from $A$ to $B$).

This show that you don't actually need to construct $G'$ entirely. You only need to compute a given bit of its adjacency matrix in logarithmic space.


Semantic Code Comparison Consider two codes that do the same thing, in the same time and memory order, But they don't do it exactly the same way. Is there any Idea for a program to declare those codes as the same?

For Example:

Change Vars 1

a = a + b;
b = a - b;
a = b - a;

Change Vars 2

int temp = a;
a = b;
b = temp;

or consider two bubble sort codes that sort ascending, one starting from the end, one from the beginning of the array.

There is the idea to execute both codes and then check if the memory status is similar after the execution of both codes. But that's not very comprehensive.

Edit: My focus is on Turing complete languages mostly.

I have two news for you. I start with the bad one.

The dark side of the question

Computation theory tells us that checking whether two programs, or
program fragments, are equivalent is not decidable.

What that means is only that there is no unique technique that can
check that equivalence of any pair of programs. This remains true if
you consider a single programming language, as long as it is Turing
complete. (Note: I do not understand what you intend when mentionning
Turing complete algorithms in your comment - and, by the way,
precisions should be integrated in the question, preferably to
comments).

No unique technique also means no unique finite set of techniques as
they could be applied simultaneously. It also means no infinite set
of techniques that is finitely describable, etc.

This can be formally proved on Turing machine with Rice theorem (which
is a bit subtle to use). The proof can be tediously transposed to any
other Turing complete formalisation of computation. But invoking
Church-Turing thesis is usually considered enough.

To summarize it, there is no way you can produce a system that will
take two arbitrary program fragments of a Turing Complete language and
tell you when they are equivalent semantically, i.e. when their
computation results are the same.

But do not despair, there is hope.

The bright side of the question

While the above is true when you make the question so general, it does
not mean that this can never be done. Actually, this, or problems very
close to it, is the object of considerable reasearch. The
undecidability statement should only be seen as a limitation to what is to
be expected, but there is considerable room within that limitation.

So, there are many situation when it is actually possible to apply a
procedure that will actually decide whether two (fragments of)
programs are actually equivalent. The applicability of such a
procedure can be defined by a language (that is not Turing complete),
or by some limitation on the computational power such fragments can
express (so that they do not have to be in the same language).

Much of the research related to type theory also concerns provability
of programs properties, and can lead to answers to your question. But
that is much outside my competence.

Many other techniques have been developed for your purpose.

About your examples

Your idea of running both codes and comparing results is a good one,
at least in simple cases, like your example.

But you have to run the code symbolically, and then use a symbolic
computation system to check that the answers are indeed the same.

So, assume that initially a==$a$ and b==$b$, where I use italics for
symbolic expressions, i.e. non evaluated formulae. The symbols $a$ and $b$ just stand for themselves, and have no associated value.

running the first code:

a = a + b; - - so a==$a+b$
b = a - b; - -  so b==$(a+b)-b$
a = a - b; - -  so a==$(a+b)-((a+b)-b)$

Recall, again, that what is in italics is just symbolic expressions, trees if you prefer. There is nothing to be computed.

running the second code:

int temp = a; - -  so temp==$a$
a = b; - -  so a==$b$
b = temp;; - -  so b==$a$

Now you give these results to a symbolic calculator that check that
the values of variables a and b are the same at the end. It must be able to simplify expressions such as $(a+b)-b$ and $(a+b)-((a+b)-b)$ to respectively $a$ and $b$, which requires using known algebraic properties of the operators $+$ and $-$.

It is actually a good technique (when applied properly - I goofed my first try),as it allowed me to notice that your two codes were not equivalent, and I corrected the first one.

Running the code symbolically is an example of a general paradigm
called abstract interpretation. The "casting out nines" test is a very
elementary example of these techniques.

Symbolic evaluation and abstract interpretations are a well
studied way of proving things about programs.

It is pretty much what is done by type checkers.

But it is far from the whole story about proving things about programs.
Large systems are being developed to prove properties of programs by
different means.

In other cases (probably for your sorting examples), it may be better to have a specification of what the
program is supposed to do and separately prove the two pieces of code
conformant with that specification. This avoid having to consider
simultaneously the specifics of two algorithms.


IS $LOGSPACE\subsetneq QMA$ an open problem? Having read some chapters of Computational Complexity: A Modern Approach, I see no time or space hierarchy theorem which applies to this case. As far as I can see, we know the following inclusions:

$L \subseteq NL \subseteq P \subseteq BPP \subseteq BQP \subseteq QMA$

but no inclusion is known to be strict, and it is not known whether at least one of these inclusions is strict. The statements $L=P, P=BQP, BQP=QMA$ are all unsolved, so I am free to conjecture that they are all true, or all false. I know that it is absolutely obvious that $L\subsetneq QMA$, because to go from one to the other one must (1) remove the logarithmic space bound, (2) introduce randomness to the algorithm, (3) add quantum and (4) add nondeterminism.
This question is interesting because each of these augmentations is believed but not proved to add computational power (with the possible exception of (2)), they correspond to their respective flagship inclusions above, and this question captures all of them simultaneously, showcasing an enormously long distance unsolved relationship. It is also interesting because to my knowledge it is the longest-distance unresolved inclusion between two natural complexity classes (classes that arise naturally in studying theory and which capture fundamental notions of resource-bounded computation, but this point is subjective).

The only strict inclusions I can find are $L\subsetneq Space(n) \not= NP$ and $L \subsetneq PSPACE \supseteq P$. The first is not satisfying because $Space(n) \subsetneq NP$ is open.

This also begs the question, alright if these augmentations individually are hard to reason about, but surely you cannot add them all at once without changing your complexity class? And is it easier to prove such weaker strict inclusions?

(and, tongue in cheek, if the answer to my question is yes, what have complexity theorists been up to the past few decades?)

Widely open, I can tell. $\mathrm{QMA}\subseteq\mathrm{PP}$ is known. But, $\mathrm{PP}$ has been only separated from $\mathrm{uniform}$-$\mathrm{TC}^0$ up to now. So, even the stronger claim $\mathrm{L}=\mathrm{PP}$ is still unrefutable.

From the Wikipedia article https://en.wikipedia.org/wiki/PP_(complexity)#PP_compared_to_other_complexity_classes, $\mathrm{PP}$ strictly contains $\mathrm{TC}^0$, the class of constant-depth, unbounded-fan-in uniform boolean circuits with majority gates. (Allender 1996, as cited in Burtschick 1999)

Allender, E. (1996). "A note on uniform circuit lower bounds for the counting hierarchy". Proceedings 2nd International Computing and Combinatorics Conference (COCOON). Lecture Notes in Computer Science. 1090. Springer-Verlag. pp. 127–135

Burtschick, Hans-Jörg; Vollmer, Heribert (1999). "Lindström Quantifiers and Leaf Language Definability". ECCC TR96-005