Are there any problems in $P$ which we do not know any $P$ algorithms? A problem in $P$ is one that can be solved in polynomial time (or faster) on a deterministic Turing machine. Now if I am correct, there is nothing here referring to the algorithms - which can themselves can be given a complexity class (necessarily greater or equal to that or the problem).

My question is: Are there any problems in $P$ for which we do not know the existence of any algorithm in $P$.

I am physicist by training so please let me know if anything doesn't make sense.

Nice question!  I think the answer is "yes", but I can't prove it.

The answer is not obvious.  You might imagine that if we had a problem with a non-constructive proof that it is in $P$, we might know it is in $P$ without knowing of an algorithm for it.  For instance, here is a reasonable candidate for such a problem:

$$f(n) = \begin{cases} 1 & \text{if $0^n$ occurs in the decimal representation of } \pi \\ 0 & \text{otherwise.}\end{cases}$$

The problem is to compute $f$.

We can prove that $f$ is in $P$, but as far as I know, we don't know of any specific polynomial-time algorithm that we can prove correctly computes $f$.  In other words, we're certain that such an algorithm exists, but we can't write one down that we're sure works.  In particular, we know of an infinite family of algorithms, such that all of them run in polynomial time and one of them is correct; but as far as I know, we don't know which one is correct.  See How can it be decidable whether $\pi$ has some sequence of digits? for details.

So, I suspect that the answer to your question is "yes" and that $f$ is such an example.

You can find more examples at https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs. That page shows examples of problems where we can prove that a polynomial-time algorithm exists, but that proof is non-constructive, in the sense that it does not tell us what the algorithm is.  Now that said, it's possible that this just reflects our lack of current knowledge.  Maybe tomorrow someone will come up with a constructive proof that those problems are in P, i.e., maybe they will come up with a specific algorithm that they can prove is correct and runs in polynomial-time.  But as it stands today, we don't know of any such algorithm.

See also https://cstheory.stackexchange.com/q/4777/5038, https://cstheory.stackexchange.com/q/12162/5038, and Is there an algorithm that provably exists although we don't know what it is?.

At the same time, there is a limited more limited version of the question for which the answer is "no".

If you limit yourself to problems in NP that have a known nondeterministic polynomial-time algorithm, then we can say that the answer is "no" for those problems: for every problem that is known to be in P and is known to have a nondeterministic polynomial time algorithm, we know of a polytime (deterministic) algorithm for it.

It might sound crazy, but it's true.  In particular, one can use Levin universal search to write down an algorithm for such a problem.  The resulting algorithm will have constant factors that make it totally impractical, but we can prove it runs in polynomial time and that it is correct.  See What is a lay explanation for universal search?, Polytime algorithm for SUBSET-SUM assuming P=NP, and Is there a concept for an algorithm computing a function by first finding another algorithm?.


Recursive equations vs. inference rules It seems to me that recursive equations can always be presented as inference rules.  For the forward direction, an example is addition over Peono numerals (built from $O$ and $S(\_)$)

$$
\begin{align}
add(O, m)    & = m \\
add(S(n), m) & = S(add(n, m))
\end{align}
$$

which can be also presented as

$$
\frac{ }{add(O, m) = m} \qquad \frac{add(n, m) = a}{add(S(n), m) = S(a)}
$$

Is the backward conversion (from inference rules to recursive equations) always possible?  If not, it seems inference rules more general, right?  Except the superficial difference between the presentations, is there any other deeper difference between the two?

Inference rules are "more general". A recursive equation, actually any equation $E_1 = E_2$ is like an inference rule without premisses:
$$\frac{}{E_1 = E_2}$$
A general inference rule may have premisses, and so it is like a conditional equation.
Only very special kinds of inference rules may be equivalently expressed as equations. For instance, it seems difficult to express
$$\frac{a \bullet c = b \bullet c}{a = b}$$
and
$$\frac{add(x,add(y,z)) = add(x,z)}{add(y,z) = z}$$
as equations.


When is ε-removal from a CFG idempotent? For which context-free grammars is it idempotent to remove $\varepsilon$-productions?  Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\varepsilon$-productions (apart from $S \to \varepsilon$ iff $\varepsilon \in L(G)$), is this sensitive to the choice of algorithm?

As far as I can tell:

If $L(G) \not \ni \varepsilon$ then rewriting is always idempotent: the second pass finds no $\varepsilon$-productions to operate on.
If the start symbol doesn't occur on any right-hand-side it is always idempotent: after the first rewrite this property is maintained and there are no $\varepsilon$-productions except maybe $S \to \varepsilon$. The second pass may find an $\varepsilon$-production but since $S$ doesn't occur on any right-hand side there are no rules to transform.

Is there some variant of $\varepsilon$-removal which is always idempotent?  Will treating the start symbol as never nullable (even if it is) produce an idempotent $\varepsilon$-removal algorithm?  My tests suggest so, but I can't think of a proof at the moment.

Pretending the start symbol to not be nullable will lead to an $\varepsilon$-removal algorithm which is idempotent on all CFGs.  I'll now formalize and prove this.

I define a non-terminal $A$ to be S-nullable iff

It is not $S$ (the start symbol); and
It either has a rule $A \to \varepsilon$ or it has a rule $A \to X_1 \ldots X_n$ where each $X_i$ is an S-nullable non-terminal.

The $\varepsilon$-removal algorithm then becomes:

Input: A context-free grammar $G = (N, \Sigma, S, P)$.

Output: A context-free grammar $G_\varepsilon$ with no S-nullable non-terminals and $L(G_\varepsilon) = L(G)$.

Procedure: let $G' = (N, \Sigma, S, P \setminus \{(A \to \varepsilon) \in P \mid A \not= S\})$. For each non-terminal $A$ in $N$ which is S-nullable in $G$, for each rule $B \to \alpha A \beta$ in $G'$, add the rule $B \to \alpha \beta$ to $G'$ if $\alpha \beta \not= \varepsilon$ or $B = S$ ($\alpha$ and $\beta$ are strings in $(N \cup \Sigma)^*$).  Let $G_\varepsilon$ be $G'$ after all such rules have been added.

Note that one-by-one addition of rules means that if we have $S \to ABCd$ and $ABC$ is nullable and we nullify $A$, $B$, $C$ in that order, we will first add $S \to BCd$, then add $S \to ACd$ and $S \to Cd$, then add $S \to ABd \mid Bd \mid Ad \mid d$.  In other words, it should be equivalent to doing the combinatorial expansion of rules one rule at a time.

Clearly $G_\varepsilon$ has no S-nullable rules: all $\varepsilon$ rules were removed (except $S \to \varepsilon$ if it was there), and no $\varepsilon$ rules were added (except maybe $S \to \varepsilon$).  Hence no non-terminal is S-nullable directly (since $S$ is never S-nullable), and the inductive case has no basis to apply to.

Hence the algorithm is idempotent: it only adds or removes rules if there is an S-nullable non-terminal in $G$.

Also the algorithm preserves language, i.e. $L(G_\varepsilon) = L(G)$, by translation of derivations.

When we derive $A \Rightarrow \varepsilon$, we can instead avoid introducing $A$ in the first place, unless $A = S$ in which case $S \to \varepsilon$ is a rule.  In the other direction, when we derive $\alpha \beta$ we can sprinkle it with (S-)nullable non-terminals and derive $\varepsilon$ from those.

Once more, with formality:

In one direction, when $\alpha \beta$ is derived from $A$ in $G_\varepsilon$ and $A \to \alpha \beta$ doesn't occur in $G$, this is because we added this rule based on finding $A \to \alpha B \beta$ with $B$ S-nullable. Either this rule occurs in $G$, in which case derive $\varepsilon$ from $B$, or this rule was itself added; let $\alpha' \beta' = \alpha B \beta$ such that we added $A \to \alpha' \beta'$ based on finding $A \to \alpha' C \beta'$ where $C$ is S-nullable.

Every inductive step searches for a right-hand side that's longer by 1 and bounded by the length of the longest rule in $G$, hence this process terminates.  Derive $\varepsilon$ from all the back-filled non-terminals (they're all S-nullable).  This will derive $\alpha \beta$ from $A$ in multiple steps, hence $\Rightarrow^*$ is preserved (in one direction).

In the other direction, if $\varepsilon$ is derived from $A$ (in a single step) where $A \to \varepsilon$ doesn't occur in $G_\varepsilon$, we know that $A \not= S$ (because we never remove $S \to \varepsilon$) and $A$ is S-nullable; hence we must have previously derived some sentential form containing $A$ in at least one derivation step.

Let $B \to \alpha A \beta$ be the rule which introduced the $A$ in question.   If $\alpha \beta \not= \varepsilon$, we added the rule $B \to \alpha \beta$. Use this rule instead.  (Any derivations performed between introducing and eliminating $A$ can still be performed, and have identical results.)

If $\alpha \beta = \varepsilon$, then either $B = S$ or $B$ is S-nullable.  If $B = S$ we added the rule $S \to \varepsilon$; use this to replace the derivation $\gamma \underline{S} \delta \Rightarrow \gamma A \delta$ with $\gamma \underline{S} \delta \Rightarrow \gamma \delta$.

If $B \not= S$ it is S-nullable (as $B \Rightarrow A \Rightarrow \varepsilon$) and some other rule introduced $B$ to our sentential form. Apply the same replacement; the number of recursive steps is bounded above by the number of derivation steps done so far.

Unrelated observation: if in $G$ we have rules $S \to \varepsilon$ and $A \to \alpha S \beta$ then $G_\varepsilon$ will still have those rules, i.e. it will not be essentially non-contracting.  However, if $S$ never occurs on the right-hand side of any rule in $G$, then $G_\varepsilon$ will be essentially non-contracting (and $S$ will also not occur on any right-hand side in $G_\varepsilon$).


Do you have to do reduction both ways to prove a problem is NPC? Also, what's the difference between transforming a problem into another problem and doing a reduction? They sound synonymous to me. Thank you!

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


Find disjoint contiguous sub-arrays in better than $\mathcal O(n^2)$ Given an array of integers. Find two disjoint contiguous sub-arrays such that the absolute difference between the sum of two sub-array is maximum.

The sub-arrays should not overlap and it can not be empty.

eg [2 -1 -2 1 -4 2 8]

ans (-1 -2 1 -4) (2 8)

diff = 16

Better than $\mathcal O(n^2)$ solution was expected.

This is a complete re-edit of my previous solution, which erroneously focused on partitions, not on arbitrary sub-arrays.

This problem seems to be an interesting variation on the Maximum subarray problem, which consists of finding the subsequence of values with the largest sum in an array.

Given an array a of integers, finding the maximum subarray can be done as follows:

int best_left = 0, best_right = -1, best_sum = INT_MIN;
int i, curr_left = 0, curr_sum = 0;
for ( i = 0 ; i < N ; i++ ) {
    curr_sum += a[i];
    if ( curr_sum < a[curr_left] ) {
        curr_sum = 0;
        curr_left = i+1;
        }
    else if ( curr_sum > best_sum ) {
        best_left = curr_left;
        best_right = i;
        best_sum = curr_sum;
        }
    }

The above code is untested. The largest summing interval should then be [best_left,best_right].

To solve your problem, you could sweep from left to right and store the values best_left and best_sum for each position i in the array, effectively giving you the largest sub-array from 0 to i for each i.

At the same time, you could flip the signs in the above code and also store the minimum subarray from 0 to i for each i.

Now imagine doing the same thing again, yet this time traversing the array backwards, from right to left, also storing the minimum and maximum subarrays as you go along.

Once you've constructed both sets of indices, you can traverse them and find the point which partitions the array such that the difference between the minimum/maximum subarray on either side is largest.


Growth of exponential functions according to the big O notation I'm preparing for an exam and trying to make some sense of the growth of the different exponential functions. I picked the trickiest functions for myself and tried to sort them according to the big O notation. Since it's hard to use L' Hospital's rule on exponential functions I at least want to get a feeling for the order of growth.

$$
n^2 = O(ln(n) ^ {ln(n)}) = O(n^{ln(n)}) = O(2^{\sqrt{n}})=O(2^{(n/2)}) = O(n ^{\sqrt(n)}) = O(n!) = O(n ^n)
$$

I'm particularly unsure about the right place of fac(n). Can anyone verify if that is correct?

You swapped two functions. Notice that:
$$n^{\sqrt{n}} = 2^{\sqrt{n} \log n } = o(2^{\frac{n}{2}})$$.

Once this is fixed, the factorial is in the correct order since very rough inequalities show that
$$n! = n \cdot (n-1) \cdot \ldots \cdot 2 \ge \underbrace{2 \cdot 2 \cdot \ldots \cdot 2}_{n-1 \text{ times}} = 2^{n-1} = \omega(2^{\frac{n}{2}}),$$
and
$$n =  n \cdot (n-1) \cdot \ldots \cdot 2 \le \underbrace{n \cdot n \cdot \ldots \cdot n}_{n-1 \text{ times}} = n^{n-1} = o(n^n).$$

In general, from Stirling's approximation you know that $n! = \Theta( \sqrt{n} \cdot (n/e)^n )$.


Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$ I have found two interesting questions regarding the quotient of languages, described as:
$A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
The first one is:

Let $A$ and $B$ be regular languages, prove that $A/B$ is decidable

By using the proof from this other question, it can be proved that $A/B$ is regular if $A$ is regular too.
Then, since any regular language is decidable, $A/B$ will be regular (and decidable) too.
The second one is:

Let $A$ and $B$ be decidable languages, prove that $A/B$ is semi-decidable

I have no idea on how to prove this one, I assume that it's somehow related to $A$ and $B$ being able to stop for any string, whether it's accepted or rejected, but since I don't know whether $A$ is regular or not, I don't know what to do.

Let $\Sigma$ be your alphabet. You want to design a Turing machine $T$ such that, given any word $w \in \Sigma^*$, $T(w)$ accepts if and only if $w \in A / B$. Notice that since you only want to prove that $A/B$ is semi-decidable, $T(w)$ is not required to reject when $w \not\in A / B$.
Since $A$ and $B$ are decidable, you know that there are two Turing machines $T_A$ and $T_B$ such that that $T_A(x)$ (resp. $T_B(x)$) accepts if $x \in A$ (resp. $x \in B$) and rejects otherwise.
You can then design $T$ as follows:

For each word $z \in \Sigma^*$:

If $T_B(z)$ accepts and $T_A(wz)$ accepts:

Accept.


If L is context-free, must FH(L) be context-free? Define $FH(L) = \{x \in \Sigma^* : \exists y \in \Sigma^* \text{ with } |x| = |y| \text{ such that  } xy \in L\}$.  In other words, $FH(L)$ is the set of first halves of even length strings in $L$.  Given this, if $L$ is context-free, must $FH(L)$ be context-free?

Here's my attempt at a proof:
Since $L$ is a CFL, there exists a non-deterministic PDA recognizing $L$, $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$, where $\Sigma$ is the input alphabet, $\Gamma$ is the stack alphabet, and $Z_0$ is the symbol representing the initial stack contents.  Construct PDA $M'$ from $M$, with $M' = (Q', \Sigma, \Gamma, \delta', q_0', Z_0, F')$, defined as follows:

$Q' = {q_0'} \cup (Q \times \Gamma_{\varepsilon}) \times (Q \times \Gamma_{\varepsilon}) \times (Q \times \Gamma_{\varepsilon})$.
$F' = \{[(q,X),(q,X),(p,Y)] : X,Y \in \Gamma_\varepsilon \text{ and } p \in F\}$
$\delta'(q'_0, \varepsilon, \varepsilon) = \{([(q,X), (q_0,Y), (q,X)], \varepsilon) : q \in Q \text{ and } X,Y \in \Gamma_\varepsilon \} $
$\delta'([(q,X),(p,Y),(r,Z)], a, \varepsilon) = \{([(q,X),\delta(p,a,Y), \delta(r,b,Z)], \varepsilon): X,Y,Z \in \Gamma_\varepsilon\ \text{ and } b \in \Sigma\} $

The first component of a state in $Q'$ records the guessed state $q$ and does not change once it is initially recorded.  The second element records what state we are in after having processed some prefix of the input x, starting from state $q_0$, and the third element records what state we are in  after having processed some prefix of the guessed $y$, starting from $q$.
I am not sure if this proof works, because I am a bit confused as to what to do with the stack for $M'$.

The intuition developed in the comments is right. The answer is NO, there is a counter-example, a CFL for which the first halves are not CFL.

$L = \{ a^m b^n c^n a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c\}$, from the answer on our sister site.

   Proof by Pumping lemma: pick $a^p b^p c^p \in \mathrm{FH}(L)$; pumping either destroys the "$b^n c^n$"- or the "first half"-property.

A slight adaptation of that language is
$K = \{ a^m b^n c^n \#\# a^{3m} \mid m,n\ge 1 \}$, over the alphabet $\{a,b,c,\#\}$. We can now "force" the point where the cutting site of the first half is and get another proof technique.

   Let $H = FH(K) \cap a^*b^*c^*\#$. This means we only consider first halves where the middle is exactly at the point between the two $\#$-symbols. Thus. $m+2n+1=1+3m$, or $m=n$. Thus $H=\{a^nb^nc^n \mid n\ge 1\}\#$. Now if $K$ is context-free then $H$ is context-free (via the closure property intersection by regular languages). This language is close to a standard non-context-free example $\{a^nb^nc^n \mid n\ge 1\}$. This in turn can be obtained by right quotient with $\#$ which also preserves context-freeness.


Minimum time to assemble multipart object I've been asked to do this task in an online assessment. I've passed, so my solution is supposedly correct, but I am unable to prove it. The task is:

Given a set of parts (array of integer part sizes), worker must put them all together. Parts are assembled in pairs. To put together two parts of sizes A and B worker needs A+B minutes. The resulting part's size is also A+B. Write a program to determine the minimum time required to put together given set of parts.

My solution was:

MinHeap h
for p in parts:
  h.push(p)
time = 0
while h.size() > 1:
  v1 = h.pop()
  v2 = h.pop()
  time += v1 + v2   ### assembly time
  h.push(v1 + v2)   ### adding new part
return time

This solution passed all tests.

Question:

Does this solution produce correct min time, and if yes, how to prove it?

Your solution (of greedily merging the two smallest objects available) is indeed correct. This problem is very classic and you can find it under the name 'rod connection' or 'rope connection'. Here (https://stackoverflow.com/questions/43715207/how-to-prove-this-greedy-algorithm-as-optimal-rod-connection) is the proof of optimality.


How to solve a DP problem that minimizes a sum of cubic powers? I am trying to practice some coding problems and I came upon this problem:

As electricity prices are soaring, there must be a way to reduce wastage by increasing the utilization of heavy duty machines, such as elevators.
We formulate the problem as follows.
There are $N$ persons $ (p_1,...,p_N)$ waiting in a queue to get into an elevator. By the way, there is only one elevator, and it travels between the ground floor to the sky floor (i.e., there are no other stoppages in between). Also, all persons are waiting on the ground floor.
Just for simplicity, we are concerned only with the utilization of the ground-to-sky journey of the elevator. Each person $p_i$ has a positive weight $w_i$.
The weight capacity of the elevator is $M$. Therefore, all persons may not be carried together. They are carried in several trips. Each person gets into the elevator according to his order in the queue. Meaning, $p_1$ gets in first, then $p_2$ and so on. Suppose at the $t$-th trip, persons $p_j$ through $p_k$ gets into the elevator. The waste factor ($WF$) of the trip $t$ is defined as

$$WF[t]=M-\sum_{i=j}^k(w_i).$$

Your task is to minimize the total waste ($TW$), which is defined as:

$$TW=\sum_{t=1}^{S-1}(WF[t])^3,$$

where $S$ is the total number of trips required to carry all the people from the ground to the sky floor. Note that the $WF$ of the last trip is not included in the $TW$ calculation.

I got completely stuck here, I figured that this can be solved via DP but I don't know how. Especially with the condition of maintaining the order.
Full problem can be found in here Problem K: Elevate the Utilization!

The essence of the dynamic programming is to recognize the appropriate subproblems.
Here is a way to formulate the subproblems. Let us compute $dp[i]$, the minimum total waste for weight sequence $w_{i}, w_{i+}, \cdots, w_N$, where $1\le i\lt N$. The wanted minimum total waste of the entire sequence shall be $dp[1]$.
The base cases are $dp[N]=dp[N-1]=\cdots=0$, where $dp[i]=0$ as long as $w_{i} + w_{i+1}+ \cdots+w_{N}\le M$ since the last trip does not produce waste. Let $j$ be the smallest such index.
What about $dp[j-1]$, $dp[j-2]$ and beyond? We note that $dp[k]$ is the minimum of
$$\begin{align}
  dp[k+1] &+ (M-w_k)^3,\\
  dp[k+2] &+ (M-(w_k+w_{k+1}))^3,\\
  \cdots\\
  dp[k+t] &+ (M-(w_k+w_{k+1}+\cdots+w_{k+t-1}))^3\\
  \cdots,\\
  \end{align}$$
where the list goes on as long as $w_k+w_{k+1}+\cdots+w_{k+t-1}\le M$.
This recurrence relation enables us to compute $dp[k-1]$ if $dp[k], dp[k-1], \cdots, dp[N]$ are known.
The time complexity of algorithm is about $O(N*N)$.
Java code

The above is an implementation in Java that takes file "elevate.in" as input. Just click "run" to see the result.
Exercises
Here are two exercises based on the same situation to think about.
Exercise 1. (One minute or two.) Suppose the total waste is defined as $$TW=\sum_{t=2}^{S}(WF[t])^3$$ instead. Note that the WF of the first strip instead of the last strip is excluded.
Exercise 2. Suppose the total waste is defined as $$TW=\sum_{t=2}^{S-1}(WF[t])^3$$ instead. Note both the WF of the first strip and the last strip are excluded.


What is the most effective way to learn, understand, and utilize an algorithm? In order to keep my interviewing skills sharp, I solve one algorithm/data-structure problem every day, from sites like Leetcode or HackerRank.

If I am not able to solve it after 45 minutes or so, I usually refer to the solution. I review it, understand it, and move on.

However, I have found that I do not really learn anything at all by looking at the solution. Even though I understand the solution at that point in time, it doesn't really stick with me. I am not able to learn the approach and trick of that solution, for purposes of retaining and utilizing it later. And, if I ran into a similar question in the future, I would not remember how to utilize the approach that I have definitely seen before.

What is your technique or suggestion in learning such approaches/techniques in solving algorithm/data-structure problems?

If this question is not in the right Stack Exchange please let me know.

To be an algorithm designer, you have to do some steps.

First, learn the basics of algorithmic thinking. You can learn it by using a simple programming language book. Choosing the language is not important. You can take a look at this page for finding a book. After finishing this step, you have to be able to present pseudocode (or code written in a specific language) for simple problems, for example:

Searching in a list: there is a list of numbers, and we want to see a specific number is in the list or not.
Sorting a list
Finding the greatest common divisor of two numbers

Second, learn the important data structures— link-list, stack, queue, and tree— and their algorithms. For doing this step, you can read the books of data structure written for bachelor students of computer science. For example, Fundamentals of Data Structures by Ellis Horowitz and Sartaj Sahni is a good book. At the end of this step, you have to know/do the following things:

What is a data structure? How we can iterate over the elements of a data structure? How we can add a new item(/remove an item) from the data structure?
What are the main features of each data structure?

Third, learn conventional algorithm design techniques— divide and conquer, dynamic programming, greedy, back-track, branch and bound. For doing this step, you can read the algorithm design books written for bachelor students of computer science. For example:

Foundations Of Algorithms, Richard Neapolitan
Introduction to Algorithms, Thomas H. Cormen, et al. (Chapters 1-17)
After doing this step, you can solve a large range of algorithmic problems, like the problems that can be found on this website: onlinejudge.org.

Forth, learn specialized algorithm design techniques, like randomized algorithmic techniques, parallel algorithmic techniques, distributed algorithmic techniques, approximation algorithmic techniques, etc. For each case, there are some books written for graduate students of computer science.

Besides, there are some other steps, like learning the basics of the theory of computing, complexity classes (NP-complete and P-complete theories), and a lot of other things. It depends on your goal and the level that you want to be reached.


Shortest path from that passes through a set of edges once Given a graph with weighted edges. How to find the shortest path from vertex $A$ to vertex $B$ that passes through a set of edges $X$ at most once? $X$ can be big.

Slow solution:
Finding shortest path from $A$ to each edge of $X$ and shortest path from each edge to $B$ in graph $G\setminus{X}$. Combining those paths and choosing the shortest one.

Can anyone think of a faster solution that doesn't require running Dijkstra's algorithm for each edge from $X$?

Assumption: Since you talk about Dijkstra, I assume you have non-negative edge weights.

Remember that Dijkstra already computes shortest paths to all other nodes. That is, after two runs -- one with $A$ and one with $B$ as starting node¹ -- you have shortest paths from $A$ to all nodes incident to $X$, and from $B$ to all nodes incident to $X$.

We just have to make sure that there are no edges from $X$ on these paths. The idea is to make edges from $X$ so expensive that choosing all other edges is better than picking just one edge from $X$. That actually pretty straight-forward to do.

Let $W = 1 + \sum_{e \in E} w(e)$; then modify the weights so that

$\qquad\displaystyle w'(e) = \begin{cases} w(e), &e \not\in X;\\W + w(e), &e \in X.\end{cases}$

A shortest path w.r.t. $w'$ of weight $<W$ is shortest w.r.t. $w$ when ignoring paths that hit $X$; if it has larger weight there is no path that avoids $X$ between the two nodes.

Now, if the shortest path from $A$ to $B$ you find by the two Dijkstra runs has weight $<W$, it is one contender for the shortest path. In addition, you have to find the best pair of paths that connect $A$ and $B$ to different ends of an $X$-edge. Combine for all $e \in X$ the shortest paths to $A$ and $B$, and add the original weight $w(e)$.

Note that there are two pairs of paths for each such $e$! That is, we get $2|X|+1$ paths to chose to minimal one from².
So that is an additional $\Theta(|X|)$ effort, which is dominated by the initial runs of Dijkstra.

In total, this solves your problem with two Dikjstra runs and one graph modification that can be performed in $\Theta(|E|)$, or even on-the-fly if your algorithm is implemented with nice abstractions.

This only works in undirected graphs. If your edges are directed, you need to perform the second run on an reversed copy of $G$.
If there is none with weight $<W$ then the original graph doesn't have any path from $A$ to $B$ that hits $X$ at most once!

This answer saw heavy revision. While the ideas were all there from the start they were presented as two solutions, neither of which worked on its own. Credits to Draex_ for picking the post apart!


String Comparison vs. Hashing I recently learned about the rolling hash data structure, and basically one of its prime uses to searching for a substring within a string. Here are some advantages that I noticed:

Comparing two strings can be expensive so this should be avoided if possible
Hashing the strings and comparing the hashes is generally much faster than comparing strings, however rehashing the new substring each time traditionally takes linear time
A rolling hash is able to rehash the new substring in constant time, making it much quicker and more efficient for this task

I went ahead and implemented a rolling hash in JavaScript and began to analyze the speed between a rolling hash, traditional rehashing, and just comparing the substrings against each other.

In my findings, the larger the substring, the longer it took for the traditional rehashing approach to run (as expected) where the rolling hash ran incredibly fast (as expected). However, comparing the substrings together ran much faster than the rolling hash. How could this be?

For the sake of perspective, let's say the running times for the functions searching through a ~2.4 million character string for a 100 character substring were the following:

Rolling Hash - 0.691 seconds
Traditional Rehashing - 71.009 seconds
Just comparing the strings (no hashing) 0.100 seconds

How could the string comparing be so much faster than the rolling hash? Could it just have something to do with the particular language I tested this in? Strings are a primitive type in JavaScript; would this cause string comparisons to run in constant time?

One possible hypothesis:

Javascript is interpreted, which can slow things down.

When you compare two strings, this will invoke a string comparison routine that is coded directly in assembly language or C, and thus string comparison will probably be about as fast as the architecture can possibly compare strings.  In contrast, when you hash strings, you have to execute multiple instructions in Javascript, which might incur overhead from an interpreter.

Another possible hypothesis:

Numbers in Javascript are a floating-point type.  There is no integer type in Javascript.  Your rolling hash probably involves what looks like integer arithmetic.  However, under the covers this is probably getting interpreted as operations on double-precision floats, which can be a bit slower.  This might also make your hash-based schemes slower.  Some Javascript engines might optimize this to integer arithmetic in certain circumstances, but no guarantees about whether any particular Javascript engine will or won't be able to do that in any particular case.


Showing Maximum Independent Set is $NP-hard$ I've read about Maximum Independent Set problem being both $NP-hard$ and $CoNP-hard$.
I know this can be shown using reduction from the corresponding Max-Clique problem, But I'm wondering - Is that the most straight forward reduction? Is it can also be shown directly from Clique problem?

Clique is the decision version of Maximum Clique, which is an optimization problem:

Clique: Given a graph $G$ and an integer $k$, decide whether there is a $k$-clique in $G$.
Maximum Clique: Given a graph $G$, find the maximum size of a clique.

Let me mention that these names are not standard. Other people might use Clique or Maximum Clique to refer to slightly different problems. Optimization problems and their decision versions are often confused in the literature, since usually it is clear from context which of the two is referred to.

There is a canonical way to convert an optimization problem to a decision problem, demonstrated above. This conversion ensures, in most circumstances, that the decision version is in NP.

We say that an optimization problem is NP-hard if its decision version is. To show that Maximum Independent Set is hard, you really need to show (by definition) that Independent Set is hard; and this you can do by reduction from Clique (not Maximum Clique).

Also, Clique and Independent Set are really the same problem — you get one from the other by complementing the graph.

Finally, let me stress that Independent Set is NP-complete, but it is not known to be in coNP or to be coNP-hard; indeed, it is conjectured not to be in coNP and not to be coNP-hard (otherwise NP=coNP).


How to put elements in allowed bags? Let's say I have a list of "Items"

I also have a list of "Bags". Each bag is a set of "Items" which gives what item can be placed in that bag. But only one item can go in each bag.

I want to place all items in a bag. It's okay if there are empty bags left over.

Does this sort of problem have a name and a solution other than a naive depth first search (a link in the direction of such an approach will be fine)?

This problem is call "$X$-satuated bipartite matching" or Hall's marriage problem, which is discussed at here on Wikipedia.

Consider each item as a woman. Each bag is a man. If item $a$ is allowed to be placed in bag $x$, it means woman $a$ and man $x$ can be married happily. Only one item can go in each bag corresponds to the assumption of monogamy, a man with one wife and a woman with one husband. So the problem is asking whether it is possible that all women can be married happily.

Please check the link for details and much more interesting result around. You can find various efficient algorithms to solve the problem and related problems.

Since we are here, we should mention the following celebrated theorem.

  Hall's Marriage Theorem — A family $S$ of finite sets has a transversal if and only if $S$ satisfies the marriage condition.


Checking claim in paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al In the 2004 paper "A Read-Only Transaction Anomaly Under Snapshot Isolation" by Alan Fekete et al. (which can be found here and here) the authors state:

  We also note that any execution of T1 and T2 (with arbitrary parameter values) without T3 present will always act serializably.

I have tested this claim inside PostgreSQL, like this

create table variables (
    name char(1) not null,
    value integer not null
);
insert into variables values ('x', 0), ('y', 0);

T2: begin
T2: set transaction isolation level serializable;
T2: select * from variables where name = 'x'
T2: select * from variables where name = 'y'
T1: begin
T1: set transaction isolation level serializable;
T1: select * from variables where name = 'y'
T1: update variables set value = 20 where name = 'y'
T1: commit
T2: update variables set value = -11 where name = 'x'
Connection reset. Reconnect (Y/n):

but as shown, when executing the T2's update, this transaction is aborted (I know this because the client, in the case pgcli, disconnected), which means that the schedule was not serializable.

What is happening here? Is the authors claim wrong? Is it a bug inside PostgreSQL? Or most probably, I made some mistake I am not aware of?

Thanks

The claim in the paper is true (I never doubt about it, but just wanted to know why) because only the dependencies between the reads and writes of concurrent transactions determine if these are serializable, but not their commits (nor their aborts, obviously).

In the example above, extracted from the paper's claim, the fact that PostgreSQL aborts T2 has nothing to do with serializability between T1 and T2, but only with some design decision in PostgreSQL that I ignore (if someone knows I, please write a comment to this answer).


Boolean circuit with two inputs and advice input is hard-wired Claim : $\cup_{c,d} $ DTIME$(n^c)/n^d \subseteq$ $P_{poly}$

Proof : if $L$ is decidable by a polynomial-time Turing machine $M$ with access to advice family $\{\alpha_n\}_{n\in \mathbb{N}}$ of size $a(n)$, then we can use the cook-levin construction for every $n$ a polynomial-sized circuit $D_n$ such that on every $x \in \{0,1\}^n$, $\alpha_n \in \{0,1\}^{a(n)}$, $D_n(x,\alpha) = M(x,\alpha)$. That is, $C_n$ is equal to the circuit $D_n$ with the string $\alpha_n$ "hard-wired" as its second input.

Question : I am not getting the part that circuit is going to have two inputs one hard-wired as second input. How a circuit will like with two inputs. I have seen circuits with one input but not with two inputs (i.e. one input is hard-wired). I am thinking that it may be the case that they are attaching advice bit to each of AND and OR gate (increasing the fan-in). So I am not getting, how they are hard-wiring the advice string ?

Reference : http://theory.cs.princeton.edu/complexity/book.pdf

Just imagine the circuit $D_n(x,\alpha)$ has $n+a(n)$ bits of input, where the first $n$ bits are treated as the first parameter for the machine $M$, and the last $a(n)$ bits are treated as the advice. To forget about this separation and have a simpler notation, we just say $D_n$ accepts two inputs. Now fix the "second parameter" with the correct advice $\alpha_n$, and this induces a polynomial circuit for $L$ with $n$ inputs.


Multiprocessor Scheduling is NP-Complete Consider this version of MS where we have set $A$ of tasks, $l(a)$, length of each task in $A$ and $m$ number of processors and also a deadline $D$. The question is where we can partition A into m disjoint subsets,  $A = A_1 \cup A_2 \cup \ldots \cup A_m$ such that we have:
$$
max \left\{ \sum _{a \in A_i} l(a): 1 \le i \le m \right\} \le D ?
$$

My attempt(Also hint from Garey & Johnson)
consider $m = 2$ and $D = \frac{1}{2} \sum _{a \in A} l(a)$. if so we have
$$
max \left\{ \sum _{a \in A_1} l(a), \sum _{a \in A_2} l(a) \right\} \le  \frac{1}{2} \sum _{a \in A} l(a) ?
$$

this implies that we should have $\sum _{a \in A_1} l(a) = \frac{1}{2} \sum _{a \in A} l(a)$ and also $\sum _{a \in A_1} l(a) = \frac{1}{2} \sum _{a \in A} l(a)$**(if we have such a partition!)**, otherwise we will have a contradiction because if for example $max$ was $\sum _{a \in A_1} l(a)$ we had $$
\sum _{a \in A_1} l(a)<  \frac{1}{2} \sum _{a \in A} l(a) \\
\sum _{a \in A_2} l(a)<  \frac{1}{2} \sum _{a \in A} l(a)
$$
and if we sum the last two inequalities we get this contradiction:
$$
\sum _{a \in A} l(a) < \sum _{a \in A} l(a)
$$

so now we know that they are equal, and we see that our problem is now an instance of partition(or subset sum with sum equal $B/2$ where $B$ is sum of all elements of A) and we know that partition is $NPC$ so our main problem is $NPC$ too by restriction.

Is my argument correct??

The deadline is maximum time a single processor can take to complete its tasks (the subset allocated to that processor) where as you are considering deadline as the total of each processor's time.

Let's say there are 6 tasks each with 1 unit of time. Then your example of taking deadline by half of total time of all tasks become 6/2 = 3. Now comes the number of processors which you take to be 2. The task now is to divide the 6 tasks into 2 groups such that the total time of each of the 2 groups is less than or equal to deadline. You cannot compare the sum of total time of each group time with the deadline as the deadline is about the maximum time a single group can take.

In terms of showing that the problem is NP-Complete, I guess you will have to show a reduction of your problem to any of the known NP-Complete problems. Intuitively, I think that this problem can be reduced to a form of subset sum problem which is NP-Complete.


How Intersection of Regular Language and a CFL is a CFL? CFL is not closed under intersection. That means, if we have L1,L2 of CFL then

L1 intersection L2 is not a CFL

And we know, all Regular languages are CFL. Then how it is true that intersection of Regular language (R1) (which is again a CFL) and a CFL(CL1) is a CFL?

R1 intersection CL1 should not be CFL right? becase R1 is again a CFL.

Every CFL language can be describes as a PDA. Every regular language can be described as a DFA.

The orthogonal product of a DFA and PDA can be defined as follows:

The new states of the automaton are all $(q_{PDA}, q_{DFA})$. That start state is $(s_{PDA}, s_{DFA})$ and the final states are all $(f_{PDA}, f_{DFA})$ where $f_{PDA}\in F_{PDA}$ and $f_{DFA} \in F_{DFA}$.

Given the transition of the PDA defined as $\delta_{PDA}(q_{PDA}, stack_{PDA}, a) = (q'_{PDA}, stack'_{PDA})$ and transition function of the DFA $\delta_{DFA}(q_{DFA})$

The transition function $\delta(q, a)$ for the new Automaton is where the transition function of the PDA is defined defined as $\delta((q_{PDA}, q_{DFA}), stack_{PDA}, a) = ((q'_{PDA}, \delta_{DFA}(q_{DFA})), stack'_{PDA})$

(in laymans terms, split out the states simulate the DFA and PDA independently and only accept the language when both are in a final state)

There is only 1 stack in this automaton. Thus it is a valid PDA. Therefor the language described by the intersection of a CFL and a regular language is a CFL.

The reason this does not hold for the intersection of 2 CFLs is because you need a second stack for second PDA.


characteristic vectors for systems The question is motivated from a physics problem:

Let's first discuss the 1D infinitely long discrete system on a lattice, a system can look like:

system 1:

...(ABAC)(ABAC)(ABAC)...

this leads to its characteristic (or correlation) vector

<A>=0.5 this is the appearing frequency of character A
<B>=0.25
<C>=0.25
<AB>=0.25 this is the appearing frequency of character AB

....

system 2:

...(AB)(AB)(AB)...

this leads to its characteristic (or correlation) vector

<A>=0.5
<B>=0.5
<C>=0
<AB>=0.5
...

Such infinite characteristic vectors may be able to uniquely correspond to any 1D system (I don't have proof)... And by using this types of vectors (its finite version), it is easier to build machine learning models based on vectors instead of the structures itself.

This idea can extend to 2D, 3D systems naturally and this is what we call cluster expansion or generalized ising model....

The problem is, in physics, system is not necessarily in a lattice:

a description of a system (for 1D) is usually:

System 3:
1, its periodicity vector
2, atomic positions inside its unit cell

for example, a 1D system can be:
1, periodicity vector (3)
2, atomic positions (A at 0, B at 1.5)

this is ---A    B     A     B---- system (atoms are only at specific coordinate, voids are everywhere else)

Is there any established theory/mathods in mathematics/computer science about its characters vectors/functions, that may be able to be used to build machine learning models? Thank you.

Yes.  You want to look at the bag-of-words model and n-gram models.

The bag-of-words model corresponds to the part of your characteristic vector: namely, the parts <A>, <B>, <C> of your characteristic vector, i.e., the frequencies of a single letter.  These are used as features for the ML algorithm.

n-gram models generalize this to a substring of length n.  For each substring of length n, we count the frequency of that substring.  These frequencies are again used as features.  For instance, we'd have a feature for the frequency of AB, the frequency of AC, and so on.

In real-world computer science, we don't deal with infinite systems; we only deal with finite systems.  (Our lifetime is finite, so a computer can only examine a finite portion of the input.)


Showing that the number of primitive-recursion programs for each function is countably-infinite Problem Statement

  Prove that if  a function $f$ is primitive recursive, then there are countably infinite number of primitive recursive definitions of $f$

Yes, this is a homework question.

My Work

I proved that there are infinite number of definitions using the following construction

$$g_k(n) = \underbrace{P_{1}^1(P_{1}^1( \dots( P_{1}^1}_{k \text{ times}}(f(n))\dots), \ \forall \ k \in \mathbb{N}$$

Here $P_1^1$ is the projection basis function which picks the $1^{\text{st}}$ element from a vector of size $1$

Now $k$ is unbounded and we will get an equivalent definition for $f$ for each $k$

Now the issue is that this is not the only way to construct an infinite number of equivalent definitions i.e. I could have also use the multiplication operator and multiplied the output of $f$ by 1 as many times as I liked.

How can I show that there is a $1-1$ correspondence of the set of all primitive recursive definitions with the set of naturals numbers? Unlike bit strings, I am unable to comprehend in what way I should assign some number to each function. In fact I don't even know in how many ways can I create equivalent definitions, so how can I even start to enumerate these functions?

Any hints?

I proved that there are infinite number of definitions using the following construction

That works in principle, but be careful about what $f$ is in that term, formally.

  Now the issue is that this is not the only way to construct an infinite number of equivalent definitions

Right you are!

  How can I show that there is a 1−1 correspondence of the set of all primitive recursive definitions with the set of naturals numbers?

You don't have to do this explicitly.
Use that the class of countable sets is closed against taking subsets.


Minimum spanning tree formulation Can any expert explain the reasoning behind the constraint in the
following formulation of the minimum spanning tree?

  To formulate the minimum-cost spanning tree (MST) problem as an LP, we associate a variable $x_e$ with every edge $e \in E$. Each spanning tree $T$ corresponds to its incidence vector $x^T$, which is defined by $x^T_e = 1$ if $T$ contains $e$ and $x^T_e = 0$ otherwise. Let $\Pi$ denote the set of all partitions of the vertex set $V$, and suppose that $\pi \in \Pi$. The rank $r(\pi)$ of $\pi$ is the number of parts of $\pi$. Let $E_\pi$ denote the set of edges whose ends lie in different parts of $\pi$. Consider the following LP:
  $$
\begin{align*}
\min &\sum_{e \in E} c_ex_e \\
\text{s.t. } &\sum_{e \in E_\pi} x_e \geq r(\pi) - 1 \quad \forall \pi \in \Pi, \\
& x \geq 0. \\
\end{align*}
$$

The constraint expresses the following fact:

  Let $T$ be a spanning tree, and suppose that we partition the vertex set into $r$ parts. There are exactly $r-1$ edges of $T$ which connect different parts.

For example, if $T$ is a tree and $C,\overline{C}$ is a cut, then exactly one edge of $T$ crosses the cut, that is, connects $C$ and $\overline{C}$.


Prove L = L(R) based on a regular expression I'm given the following language:

L = {w∈{0,1}* | w ends in 010 and contains 011}

The task is to find a regular expression R that describes this language and prove L = L(R).

I have found the regular expression : ^([011])[01]*010$.

But have no idea how to prove L=L(R)?

In the expression you propose it seems you require the string to start with 011 rather than have it as an arbitrary substring.

So in my dialect of RegEx the expression would be (0+1)*011(0+1)*010. By definition that would specify all strings of the form $u 011 v 010$ where $u,v$ are arbitrary. This means all those strings have 011 as subword and end in 010.

We also have to explain the converse. That every string with that subword and suffix is covered by the expression. For that it suffices to note that 011 and 010 cannot overlap. So, 010 must come before 011. Which means it is of the form  $u 011 v 010$.


Converting an NFA to regex using GNFA algorithm? So I've been trying to crack this for a long time and almost feel like I am going in loops about this question.

Given the following NFA:

Using the GNFA algorithm get the regular expression.

I understand that you would have the following for the first step(adding empty states):

The next step would be removing the state [q1] I would get:

Finally removing [q2] would get:

However the answers others have got is:
$(a \cup bb^*a)^*bb^*$
Which does not make sense as I got, $a^*b(b \cup aa^*b)^*$?
A GNFA(generalised nondeterministic finite automaton) is described as follows:

A GNFA is similar to an NFA but must obey certain rules:

It has only one accept state
The initial state has no transitions coming into it
The accept state has no transitions coming out from it
A transition can denote any regular expression, rather than just a
symbol from the alphabet Note that a symbol is a kind of regular
expression.

Furthermore, We may convert an NFA into a GNFA as follows:

Add a new start state with an ε-transition to the old start state
Add a new accept state with ε-transitions from the old accept states
If arrows have multiple labels, or if there are multiple arrows
between two states, replace them with the union (or) of those labels

You want to know why "the others" obtained a different expression?

When contructing a regular expression there is no unique correct answer. There are usually several expressions "that make sense". In this case you use state elimination method (I learned this under the name of Brzozowski and McCluskey). Here the order of removal determines the expression found. So: what do you get when removing $q2$ first?

You can also do "clever tricks" during the construction. In your example you have $b\cup aa^*b$ which is equivalent to $a^*b$.


On relation between FFT and polynomial multiplication Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ of length $n$ vectors with entries bound by $M$ can also be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words?

Note that the converse is trivial since polynomial multiplication reduces to $FFT$.

Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries.

$$M = |u\rangle\langle v| = \begin{bmatrix}
u_0 v_0 & u_1 v_0 & u_2 v_0 & \dots & u_{n-1} v_0 \\
u_0 v_1 & u_1 v_1 & u_2 v_1 & \dots & u_{n-1} v_1 \\
u_0 v_2 & u_1 v_2 & u_2 v_2 & \dots & u_{n-1} v_2 \\
\vdots &\vdots &\vdots & \ddots & \vdots \\
u_0 v_{n-1} & u_1 v_{n-1} & u_2 v_{n-1} & \dots & u_{n-1} v_{n-1} \\
\end{bmatrix}$$

The convolution $u \ast v$ of the two vectors is a vector of the values you get when summing along each anti-diagonal of this grid. For example:

$$(u \ast v)_2 = \sum \begin{bmatrix}
 &  &  &  &   & & u_{n-3} v_0 & 0 & 0\\
 &  &  &  &   & u_{n-4} v_1 \\
 &  &  &  & \ddots \\
 &  &  & u_2 v_{n-5} &  \\
 &  & u_1 v_{n-4} &  &  \\
u_0 v_{n-3} &  &  &  &  \\
0 &\\
0&
\text{ }
\end{bmatrix}$$

We can also think of the FFT of a vector as summing entries in a grid defined by multiplying two vectors' entries. The second vector is the sequence of roots of unity.

$$M = | u \rangle \langle e^{\tau i k/n} |\begin{bmatrix}
u_0 & u_1 & u_2 & \dots & u_{n-1} \\
u_0 e^{\tau/n} & u_1 e^{\tau/n} & u_2 e^{\tau/n} & \dots & u_{n-1} e^{\tau/n} \\
u_0 e^{2\tau/n} & u_1 e^{2\tau/n} & u_2 e^{2\tau/n} & \dots & u_{n-1} e^{2\tau/n} \\
\vdots &\vdots &\vdots & \ddots & \vdots \\
u_0 e^{-\tau/n} & u_1 e^{-\tau/n} & u_2 e^{-\tau/n} & \dots & u_{n-1} e^{-\tau/n}
\end{bmatrix}$$

The Fourier transform doesn't track along the diagonals, though. Its row-hop is different from its column-hop. For the $k$'th entry of the output we go through each column $c$ and sum up the cell from that column and the $k \cdot c$'th row (wrapping around).

$$FFT(v)_2 = \sum \begin{bmatrix}
u_0 \\
 &&&&u_4e^{\tau/7} \\
 & u_1 e^{2\tau/7} \\
 &&&&&u_5e^{3\tau/7} \\
 & & u_2 e^{4\tau/7} \\
 &&&&&&u_6e^{5\tau/7} \\
 &&& u_3 e^{6\tau/7} \\
\end{bmatrix}$$

So our question becomes: can we somehow re-arrange our vectors so that the each-stride sums $\sum u_i v_{k \cdot i}$ correspond to the each-diagonal sums $\sum u_i v_{k-i}$? Can we turn index-multiplication into index-adding?

We can, as long as we're operating in a context that allows for a logarithm. Suppose our vector size is $n$ and $g$ is a multiplicative generator for the integers modulo $n$. Then we can use the powers of $g$, i.e. the base-$g$ discrete logarithm, to define a permutation of the non-zero elements that does most of what we need. Our transformation goes roughly as follows:

Define permuted vectors $a$ and $b$ so that $a_k = u_{g^k}$ and $b_k = v_{g^{k}}$.
Compute the convolution $c = a \ast b$. So $c_k = \sum_{d=0}^{n-1} a_d b_{k-d} = \sum_{d=0}^{n-1} u_{g^d} v_{g^{-k} \cdot g^d}$.
Now un-permute $c$, and also un-permute the sum over $d$. $x_{g^{-k}} = c_{k}$ and $e=g^d$. So $x_k = c_{\log_g k} = \sum_{e=0}^{n-1} u_{e} v_{k \cdot e}$.

In other words: define a permutation $P$ based on when indices are reached when iteratively multiplying by $g$. Permute the input vector and the vector of $e^{\tau k /n}$ powers by $P$. Convolve. Unpermute by $P$. The result is the Fourier transform.

... Except that I've ignored one important issue. Our permutation doesn't work for $k=0$, because $g^k \mod n$ is never 0. Also, $g^0 = g^{n-1} = 1$. Fixing this hole requires special-casing the edges of the grid. But hopefully I've communicated the core idea of performing an FFT by delegating the heavy-lifting to a convolution and a permutation.

Note that, if you care about bit complexity instead of the number of arithmetic operations, computing the permutation may also be an obstacle. If multiplying by $g \pmod{n}$ costs $\log n$ time, and you don't have the permutation ahead of time, then overall the algorithm will still cost $O(n \log n)$.


What's the difference between "polynomial time Turing-reducible" and "polynomial time many-to-one reducible"? The following definitions are from Li, M., & Vitányi, P. (1997). An introduction to Kolmogorov complexity and its applications (2nd ed.), pg. 38.

A language $A$ is called polynomial time Turing-reducible to a language $B$, denoted as $A\leq_T^P B$, if given $B$ as an oracle, there is a deterministic Turing machine that accepts $A$ in polynomial time. That is, we can accept $A$ in polynomial time given answers to membership of $B$ for free.
A language $A$ is called polynomial time many-to-one reducible to a language $B$, denoted as $A\leq_m^P B$, if there is a function $r$ that is a polynomial time computable, and for every $a$, $a\in A$ iff $r(a)\in B$. In both cases, if $B\in P$, then so is $A$.

Aren't the two definitions equivalent? What's the difference?

A polynomial-time many-one reduction is a polynomial Turing reduction that only calls the oracle once, and that returns the oracle's answer without any further computation.


How to use different size features in SVM? I want to train a support vector machine with some features. The problem is, one of the features is 1-dimensional (only an angle) and the other is an LBP Histogram, an 58-dimensional vector.

Therefore if I concatenate them, like this (in MATLAB) :

f = [lbp_histogram; angle];

I got a 59x1 vector, I can train SVM with these vectors, however, in this case the "weight" or "importance" of angle feature is 1/59, whereas lbp has 58/59 weight. What if I want to give them equal weights? Or better, I want to adjust the weights for best performance.
How can I change the weight?

The only 2 options I have in mind is :

Scale the angle feature with the weight like this :

angle = angle * w_angle
angle = angle ^ w_angle

Do you reccomend one of these, or any other way that I can make angle as important as lbp_histogram?

I hope I stated my problem clearly,
Thanks for any help.

I think you have a misconception.  SVM does not necessarily give the latter 58 features a weight of 58/59.  Rather, SVM learns what weights to use for each feature, based upon what helps it build the best classifier.

So, just use those features and train with them.  Don't try to find a way to manually provide different weights for the features; SVM training automatically takes care of that for you.


Iterative Depth First Search for cycle detection on directed graphs I found this pseudocode on Wikipedia, and looks very elegant and intuitive:

L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
    select an unmarked node n
    visit(n)

function visit(node n)
    if n has a permanent mark then
        return
    if n has a temporary mark then
        stop   (not a DAG)

    mark n with a temporary mark

    for each node m with an edge from n to m do
        visit(m)

    remove temporary mark from n
    mark n with a permanent mark
    add n to head of L

I am trying to write an iterative version for this using 3 marks (UNVISITED, VISITED, PROCESSED), but the lack of tail recursion really bothers me.

How should I approach this?

You could add "colors" to the nodes similar to the method done for recursive DFS found in CLRS, for example. When you instantiate each node (assuming they are objects) put a color field such that every node initially has node.color $\xleftarrow{}$ white.

The following is your pseudocode modified that I believe would help:

    L ← Empty list of all nodes, where node.color ← black (once placed here)
    while exists nodes such that node.color is white do
    select a node n such that n.color is white
    visit(n)

function visit(node n)
    if n.color is black then:
        return
    if n.color is gray then:
        stop   (back edge is found indicates cycle exists)

    mark n.color as gray

    for each node m with an edge from n to m do
        visit(m)

    mark n.color as black
    add n to head of L

The idea is that all "unvisited" nodes begin colored "white". Then, when we encounter a node, we visit it and color it "grey" while exploring it. When we are done exploring this node, we color it "black". We only call DFS on nodes with "white" color.

Also regarding implementation, in addition to the stack, you could make L a set and just do a check on the size (since you know only distinct nodes will get added to this set) and once the size is equal to the number of nodes you know you've visited all the nodes of the graph, but as is if you use the coloring eventually it'll be the case that there is no node, n such that n.color == white.


Why does the formula floor((i-1)/2) find the parent node in a binary heap? I learned that when you have a binary heap represented as a vector / list / array with indicies [0, 1, 2, 3, 4, 5, 6, 7, 8, ...] the index of the parent of element at index i can be found with
parent index = floor((i-1)/2)
I have tried to explain why it works. Can anyone help me verify this?
Took reference from Why does the formula 2n + 1 find the child node in a binary heap? thanks to @Giulio

Let's assume that each tier of the heap is an array.
T1 [                n0                 ]

T2 [      n1,                n2        ]

T3 [  n3,     n4,       n5,       n6   ]

T4 [n7, n8, n9, n10, n11, n12, n13, n14]

It may not be clear, but I want you to imagine that $n0$ is the parent of $n1$ and $n2$.
Likewise,  $n1$ is the parent of $n3$ and $n4$.
For example, the second tier's length is $2$.
i.e. $[n1, n2]$
Let's say $i$ is the global index of the node in question (i.e. the node's index if the entire tree were to be collapsed within a single array), and
$j$ is the local index of the node, i.e. the index of the node within its tier.
e.g. In the diagram above, if the node in question is $n3$, $i$ is $3$ and $j$ is $0$, because $n3$ is the first element in the 3rd tier.
i = global index of a node n
j = local index of a node n within the tier where the node exists
T = tier

The maximum number of nodes in a certain tier can be expressed by:
$2^T - 1$ // e.g. when you have 3 tiers, you can have at most 7 nodes, as $2 \cdot 2 \cdot 2 - 1 = 7$
This is because there are $2^{T-1}$ nodes in each tier (note: tier numbering in our example arbitrarily starts from $1$, not $0$) and the sum of powers of $2$ up to $n$ is equal to $2^{n+1} - 1$, as you can see here https://math.stackexchange.com/questions/1990137/the-idea-behind-the-sum-of-powers-of-2
This means that the global index of the last node in the tier is:
$i_{last} = 2^T-1-1$
While the local index of the last node in the tier is:
$j_{last} = 2^{T-1} - 1$ // since there are $2^{T-1}$ elements in tier $T$
We can now compute the global index of the first node in the tier by subtracting the local index of the last node in the tier from its global index:
$i_{first} = i_{last} - j_{last}$
$i_{first} = 2^T - 1 - 1 - j_{last}$
$i_{first} = 2^T - 1 - 1 - (2^{T-1} - 1)$
$i_{first} = 2^T - 2^{T-1} - 1$
$i_{first} = 2*2^{T-1} -2^{T-1} - 1$
$i_{first} = (2 - 1)*2^{T-1} - 1$
$i_{first} = 2^{T-1} - 1$
We can now compute the global index of a node $n$ by adding its local index and the global index of the first node in its tier:
$i = i_{first} + j$
$i = 2^{T-1} - 1 + j$
Let's now think about the parent of the node in question.
The parent, n', will be in the previous tier, T-1.
The indices in T-1 will be referred to as i', j', i'_first ...

Based on what we've shown so far, we can say that the global index of the parent node in the previous tier is:
$i_{first}' = 2^{T-1-1} - 1$
Now, for every 2 predecessor(left sibling) of the node $n$ in tier $T$ there will be 1 predecessor(left sibling) of parent node $n'$ in $T-1$. Also, given index $j$ in $T$, we know there are $j$ predecessors(left sibling) of $n$ in $T$ - i.e. the index of a node is equal to the number of its predecessors(left sibling). So we can conclude that:
$j' = floor(j/2)$
Putting it all together, we can conclude that
$i' = i_f' + j'$
$i' = 2^{T-1-1} - 1 + floor(j/2)$
Now let's rework the previous equation for the global index of parent node $n$, $i = 2^{T-1}-1+j$ to the following:
$i + 1 = 2^{T-1} + j$
Finally, let's compare that to the equation of the global index of the left-child node:
$\begin{align}
i' &= 2^{T-1-1} - 1 + floor(j/2)\\
   &= 2^{T-1}/2 + floor(j/2) - 1\\
   &= floor((2^{T-1} + j)/2) - 1\\
   &= floor((i + 1)/2) - 1      \text{//NOTE: Here we use $i + 1 = 2^{T-1} + j$ mentioned above}\\
   &= floor((i - 1)/2)\\
\end{align}$


Estimate entropy, based upon observed frequency counts Suppose I have $n$ independent observations $x_1,\dots,x_n$ from some unknown distribution over a known alphabet $\Sigma$, and I want to estimate the entropy of the distribution.  I can count the frequency $f_s$ of each symbol $s \in \Sigma$ among the observations; how should I use them to estimate the Shannon entropy of the source?

The obvious approach is to estimate the probability of each symbol $s$ as $\Pr[X=s]=f_s/n$, and then calculate the entropy using the standard formula for Shannon entropy.  This leads to the following estimate of the entropy $H(X)$:

$$\text{estimate}(H(X)) = - \sum_{s \in \Sigma} {f_s \over n} \lg (f_s/n).$$

However, this feels like it might not produce the best estimate.  Consider, by analogy, the problem of estimating the probability of symbol $s$ based upon its frequency $f_s$.  The naive estimate $f_s/n$ is likely an underestimate of its probability.  For instance, if I make 100 observations of birds in my back yard and none of them were a hummingbird, should my best estimate of the probability of seeing a hummingbird on my next observation be exactly 0?  No, instead, it's probably more realistic to estimate the probability is something small but not zero.  (A zero estimate means that a hummingbird is absolutely impossible, which seems unlikely.)

For the problem of estimating the probability of symbol $s$, there are a number of standard techniques for addressing this problem.  Additive smoothing (aka Laplace smoothing) is one standard technique, where we estimate the probability of symbol $s$ as $\Pr[X=s] = (f_s + 1)/(n+|\Sigma|)$.  Others have proposed Bayesian smoothing or other methods.  These methods are widely used in natural language processing and document analysis, where just because a word never appears in your document set doesn't mean that the word has probability zero.  In natural language processing, this also goes by the name smoothing.

So, taking these considerations into account, how should I estimate the entropy, based upon observed frequency counts?  Should I apply additive smoothing to get an estimate of each of the probabilities $\Pr[X=s]$, then use the standard formula for Shannon entropy with those probabilities?  Or is there a better method that should be used for this specific problem?

Like most things of this nature the best method is best found by empirical evaluation. One thing worth noting is that most smoothing schemes can be thought of as the incorporation of a prior into your likelihood estimate. For example if you are trying to estimate the parameter $\theta$ of a binary random variable $X$ and you have data $\mathcal{D} = \{x_1, \ldots, x_n\}$ consisting of i.i.d. realizations of $X$ then your posterior takes the form

$$
\begin{align*}
P(\theta|\mathcal{D})
&\varpropto P(\theta)P(\mathcal{D}|\theta)\\
\end{align*}
$$
Assuming $P(\theta) = B(\alpha,\beta)^{-1}\theta^{\alpha-1}(1-\theta)^{\beta-1}$, i.e., a Beta distribution and letting $n_1 = |\{x_i \in \mathcal{D} \colon x_i = 1\}|$ then we have

$$
\begin{align*}
P(\theta|\mathcal{D})
&\varpropto  \theta^{\alpha-1}(1-\theta)^{\beta-1} \theta^{n_1}(1-\theta)^{n - n_1}\\
&= \theta^{n_1 + \alpha - 1}(1- \theta)^{n - n_1 + \beta - 1}.
\end{align*}
$$
Notice the effect of the hyperparameters ($\alpha$ and $\beta$) is essentially to just add some constant to your counts of each possible outcome. So additive smoothing (at least all applications I've encountered) is really just a special case of Bayesian estimation.


What computational complexity classification does autonomous/self-driving cars belong to? Self-driving car technology continues to attract popular attention and interest in today's media, but how would a computer scientist explain the theoretical nature of the problem? For example, we are frequently told that Sudoku and Go are examples of NP-completeness and PSPACE-completeness, and a range of practical progress has been made in dealing with these two categories. So similarly with autonomous vehicles, I think laypeople people (like myself) intuitively accept that learning to drive properly is a "problem", but then, what is the underlying problem that such machine learning algorithms are trying to tackle?
I did some Googling around and found different articles and papers alluding to some parts or formal abstractions of the driving problem and/or maybe robotics being PSPACE-complete. So is that the answer basically? Or is it that the question is too vague to be answerable? Or even that there hasn't been a clear understanding yet, because the area is fairly new? I'm just really curious, but didn't find anything explaining this at a high level. But when I took CS in college, the professors would emphasize to programmers that understanding the nature of the problem can be very important, e.g. understanding if your specific problem is in P or is NP-complete, and so forth.

Complexity theory is mostly interested in decision problems and in optimization problems, and your problem belongs to neither class. Complexity theory is also interested in other resources, such as communication, but at the cost of neglecting computational complexity.
Apart from not fitting the mold of problems typically considered in complexity theory, your problem is also not well-defined. There is no accurate and formal specification of the required behavior. Without such a specification it is hard to mathematically gauge its complexity.
While it is possible to abstract some aspects of "autonomous driving" into pieces which do fit current theory, in my opinion it doesn't bring us any closer to understanding the actual difficulty of solving this problem.
Complexity theory won't help you in understanding the problem of poverty, or even the problem of writing poetry, or even the decision problem of determining whether a given poem is "good" or "bad". It is not an all-encompassing theory of reality, and as you observe, it doesn't even capture all problems in which computers are involved.
Autonomous driving, in particular, combines hardware, software, legal issues, and philosophical issues. When designing autonomous vehicles, we also design the sensors available to the software controller, the mechanical interventions it is allowed to use, the laws it complies with, and so on. All of these important and pertinent issues are beyond what computational complexity theory offers.


Probability of selecting a particular set, by sampling without replacement from a categorical distribution Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p_i$ to item $i$.  I now repeatedly sample from this distribution, until I have obtained $k$ unique objects.  I'd like to compute the probability that the set of objects obtained is exactly $\{1,\dots,k\}$.

Is there an efficient way to compute this probability, given $p_1,\dots,p_n$ and $k$?

I can see that the probability has the form

$$p = \sum_\sigma \prod_{i=1}^k {p_{\sigma(i)} \over (1-p_{\sigma(1)}) \cdots (1-p_{\sigma(1)}-\dots-p_{\sigma(i-1)})},$$
where the sum is over all permutations $\sigma \in S_k$ on $\{1,\dots,k\}$.  (Here $\sigma$ represents the order in which the items $1,\dots,k$ are selected.)  However, this formula for the probability involves $k!$ terms, so computing the probability in this way would take time exponential in $k$.  Is there a more efficient way to compute it?

Of course, without loss of generality we can assume $n=k+1$.

For each $\Sigma \subseteq [k+1]$, you can compute the probability $q(\Sigma)$ that the first $|\Sigma|$ elements to appear are $\Sigma$ using the following recurrence: $q(\emptyset) = 1$ and when $\Sigma \neq \emptyset$,
$$
q(\Sigma) = \sum_{\sigma \in \Sigma} q(\Sigma-\sigma) \frac{p_\sigma}{p_\sigma + \sum_{\tau \notin \Sigma} p_\tau}.
$$
You are interested in $q([k])$. The total computation time is $O(k2^k)$ (ignoring arithmetic), if you compute the sum in the denominator in tandem. Perhaps this could be improved to $O(2^k)$.


Showing that the set of DTMs that run forever is not Turing-recognizable The language A, that is all DTMS that run forever on input.

Would this not just be the HALT problem?

Therefore no reduction or proof is necessary, other then stating that?

ANSWER FOUND:
I think i have it, if it was Turing Recognizable, then it would be possible to determine when HALT should reject and therefore HALT would be decidable. Since it is not-decidable, then A must be not Turing Recognizable.

This is not the halting problem, the halting problem is the set of TMs that do halt, the language $A$ is the set of TMs that don't halt. It's the complement of the halting problem.

You also seem to be mistaken in that the halting problem is recognizable, it's just not decidable.


Looking for the name of this job scheduling algorithm You have a list of jobs.

Each job has a deadline and an associated profit if completed before the deadline.

Also, each job takes 1 unit of time to complete, and only one job can be completed at any given time (ie single thread)

You are required to choose which jobs to complete such that profits are maximised.

This isn't for homework, just my own interest really. I want to find any resources on this problem or algorithms to solve it. It is similar to the interval scheduling problem, but not quite the same.

Any help would be appreciated.

I don't know the name of the problem, but I do know the solution - this is the same problem that I had to solve for my algorithms course, just different terminology. The problem allows for a greedy choice. If you merely wanted a hint, then stop reading here because below is the solution.

Greedy choice: you schedule the job with maximum profit on its deadline. (If jobs should be finished before the deadline, e.g. job 1 should be done before $t = 2$, then simply subtract one from the associated deadline.)

The algorithm is pretty much working backwards in deadlines, (starting at the latest deadline) scheduling the job with highest profit available on that deadline (this boils down to the greedy choice).

I will leave the proof of the greedy choice as an exercise (read, I don't have a proper keyboard available, which isn't too great for my RSI, so I cannot write it now).


What is a clairvoyant algorithm? When talking about general data structure design, my lecture notes talk about one of the concerns being cost of operations. As well as the individual cost, it mentions amortized cost. But then it goes on to say:

  Amortized cost can be:

  absolute (e.g. for every sequence σ of operations (O(n log n))
  competitive (e.g. for every sequence σ of operations O(OPT(σ)))

  where OPT(σ) is the optimal cost of clairvoyant algorithms

I can't really make any sense of this. Googling throws up this but I can't see the relevance to data structures more generally. Can anyone help me understand the quoted text?

A clairvoyant algorithm is a (usually hypothetical) algorithm that can look into the future to guarantee that it makes the best possible decisions. The typical application is in so-called "online" problems, where the input must be processed as it arrives, before the whole input is known, or in other situations where an algorithm must act based on incomplete knowledge. The point is that the hypothetical clairvoyant algorithm would be able to make perfect decisions so you can use that as a benchmark to judge your real algorithm for the problem.

The example given in the page you link is for page replacement algorithms. You need to swap some page of virtual memory out to disk and, of course, you'd rather not swap out a page that's just about to be accessed. The hypothetical clairvoyant algorithm would know which page will not be needed for the longest time and will swap that one out; a real algorithm would have to estimate, for example by assuming that a page that has not been used for a long time will not be used again in the near future.

Now, you can do a comparison.  Suppose you have enough physical memory to hold 1000 pages and you have a process that cycles through 1001 pages accessing them in the order 1, 2, ..., 1000, 1001, 1, 2, ...  The real algorithm performs terribly in this case: when page 1001 is requested, it swaps out page 1, which is the very next page to be requested. In fact, the page the process requests is never in memory. A clairvoyant algorithm might, for example, keep pages 1–999 in memory all the time and swap in pages 1000 and 1001 as needed, giving page faults only 0.2% of the time.

Other applications of this sort of idea are things like process scheduling (in most cases, a real algorithm doesn't know what demands a process will make, so it must guess) and various auction schemes where the auctioneer uses the early bids to figure out what people are prepared to pay for an item, before selling it to the next highest bidder.  The classic pop-science application is in deciding who you should marry which, for some reason, academics call the Secretary Problem. The clairvoyant algorithm would be to magically know who your ideal partner is and marry them; the best you can do in practice is to spend a few years dating and dumping people and then marry the next person you meet who is better than all the ones you dumped.  (This carries the risk that you'll meet your ideal partner during the date-and-dump phase and then never meet anyone else that good; math doesn't always make your life better.)


Faster growing busy beaver function Standard busy beaver function draws attention to final count of nonzero symbols on tape. We could instead look at largest amount of nonzero symbols appearing on tape at any point of computation. This function's lower bound would be $\Sigma(n)$ and upper bound would be $S(n)$ (max shifts function). Was there made any research on such functions? If so, are there any known values for this?

Suppose there is a machine using $n$ states which, at some point, has $X$ nonzero symbols on the tape. One can build a machine with $O(n)$ states which simulates a run of the original machine with a tape alphabet of three symbols $\{0,1,2\}$, with the following small change: whenever the original machine changes $1$ to $0$, the new machine changes it to $2$; whenever the tape is read, $2$ is interpreted as $0$. The new machine ends up with $Y \in [X,2X]$ nonzero symbols on the tape (we get $\Theta(X)$ instead of $X$ since the simulation requires using two symbols for each original symbol). So your new function, let's call it $F(n)$, satisfies $B(n) \leq F(n) \leq B(O(n))$.


How to avoid loops/cycles in iterative deepening with linear space? Breadth first graph search adds states that have already been visited to an explored set to avoid getting stuck in loops and cycles. This is fine since breadth first search needs exponential space to keep all the nodes in memory.

One of the main reasons for using iterative deepening depth first search is to avoid the exponential space requirements. To ensure linear space you can't simply add every visited state to the explored set. How then do you avoid loops in iterative deepening graph search?

My intuition is that you could remove states from the explored set at some point? Or backtrack to the root but that seems more expensive.

The main point of Iterative Deepening is to completely search a potentially infinite (or just really huge) tree with depth first search with storage linear in the maximum you search. To detect cycles, the information that a node has been visited before must be stored somewhere. This requires exponential storage, so there is no non-exponential ID algorithm that prevents searching in cycles.

However, this may not be too bad in practice if the graph is already stored somewhere. The easiest method to do this then is simply to label the 'depth' of every node as encountered by the search, so you can detect when a cycle has been found. (This is essentially the same as depth limited breadth first search, apart from the order.)

But in general, cycle detection requires more storage, or a different algorithm that uses a bit more time. In fact, you can see a very clear time-space trade-off in many cycle detection algorithms.


Can every DFA be simulated by a PDA? Given a Deterministic Finite Automata (DFA) $M_1$, does there always exist a Pushdown Automata (PDA) $M_2$ that accepts the same language as $M_1$?  I.e. can any DFA be simulated by a PDA?  Intuitively, it makes sense to me that a PDA is more powerful since it has an arbitrary amount of memory and can therefore accept more languages than a DFA, but how could this be formally proven?

I hope this answer will help you to understand the mapping. Any DFA is also a PDA. The state transitions in the DFA are similar for PDA without stack. For every transition you perform in DFA, make the similar transition in PDA and do not push/pull from stack.

For a transition

In DFA : $\delta(q_x,0) \rightarrow q_y$

In stack : $\delta(q_x,0) \rightarrow (q_y,\epsilon)$

For accepting state

In DFA : $\delta(q_x,0) \rightarrow q_f$

In stack : $\delta(q_x,0) \rightarrow (q_f,\epsilon)$


What is the formal analysis with Simple Uniform Hashing that the load factor is $\alpha = \frac{n}{m}$ Recall the definition of the load factor is the average number of elements in a chain for hashing for a table $T$ of size $m$ (with $n$ elements in consideration). Let $n_j = T[j]$ be the size of the chain for entry $j$. In this case the definition of the load factor should be:

$$ \mathbb{E}[n_j] = \mathbb{E}[T[j]] = \alpha = \frac{n}{m}$$

I was wondering, why is the above statement correct under the Simple Uniform Hashing (i.e. the probability that any given element is equally likely to hash into any of the $m$ slots or in equations $Pr[h(k_i) = h(k_j)] = \frac{1}{m}$)? In particular, I find it difficult to understand what exactly distribution (or what random variables to define) in order to compute the expectation. What distribution is the expectation taken over with respect to?

CLRS talks about this on page 259 but they never quite explain in detail why it is $\frac{n}{m}$ or ignore (leave out) the probabilistic analysis.

After some thinking I realized that $n_j$ is a random variable and it depends on how the hash function $h$ distributes keys (and I guess also in the keys one might get). So a realization of $n_j$ will be in the set $\{ 0, ..., m-1 \}$, since the table can only have a $0$ elements up to $m$ elements. Hence to calculate the expected length of $n_j$ we compute:

$$\mathbb{E}[n_j] = \sum^{m-1}_{x=0} x \Pr[n_j = x]$$

but my question is, how does one determine the distribution for $x$?

The mean chain length is the sum of the chain lengths divided by the number of chains. The sum of the chain lengths is, by definition $n$ and the number of chains is $m$. This is by far the easiest way to calculate it, and it's true even if the SUHA doesn't hold.

But since you asked, let's look at the distribution of the chain lengths.

Suppose you're putting $n$ pigeons into $m$ pigeonholes at random. Examine one pigeon hole (say, pigeonhole number 1). The number of pigeons that are assigned to this pigeonhole follows a binomial distribution; the probability that there are $k$ pigeons in that particular pigeonhole is ${n \choose k} p^k (1-p)^{n-k}$ where $p = \frac{1}{m}$.

So the expected number of pigeons in that pigeonhole is:

$$\sum_{k=0}^{n} k {n \choose k} p^k (1-p)^{n-k}$$
$$= \sum_{k=0}^{n} np {{n-1} \choose {k-1}} p^{k-1} (1-p)^{n-k}$$
$$= np \sum_{k=0}^{n-1} {{n-1} \choose {k}} p^k (1-p)^{n-1-k}$$
$$= np \left(p + (1-p)\right)^{n-1}$$
$$= \frac{n}{m}$$

By the way, if we want to reason about the number of chains of length $k$ in a hash table, for large enough $m$, it's well-approximated by a Poisson distribution.

The expected proportion of hash slots with chain length $k$ is:

$$\hbox{Pr}(\lambda,k) \approx \frac{e^{-\lambda} \lambda^k}{k!}$$

where $\lambda$ is the load factor. Note that $\lambda$ is also the mean of a Poisson distribution, so once again, the expected value of the chain length is the load factor.

You can learn a lot from this. For example:

If the load factor is 1, the expected proportion of hash chains of length 0 and the expected proportion of hash chains of length 1 are both $\frac{1}{e}$.
If you have a hash table with $m$ slots, there is a 50% chance of a collision after you insert $\sqrt{m}$ items. (Exercise: prove this!)


What is the behavior of the given counter? I found the following question -

For the circuit shown in the figure, the delay of the bubbled NAND gate is 2ns and that of the counter is assumed to be zero

If the clock (Clk) frequency is 1GHz, then the counter behaves as a

(A) mod-5 counter
(B) mod-6 counter
(C) mod-7 counter
(D) mod-8 counter

What I can see is, in this particular case clock time period is smaller than the delay in the NAND gate. But I am unable to see how it will affect the counter exactly!

ANS: MOD8 COUNTER

It still is a mod 8 counter only. But the point where anyone can get confused is the clock speed and the nand gate delay. Basically as soon as we get 111 as the answer. the nand gate gets set to 0 and hence the reset is activated now one may argue that because of this the counter won't count further as it already has the reset pin on. However since the delay of nand gate is more than the time required for the counter to give next output thus before the nand gate could change the counter to 000. The counter would have already produced the next sequence that is 001. that would help it get out of the reset configuration. Steps can be written as follow:-

counter produces 111
nand gate receives 111 and starts processing it
counter produces 000
nand computes 0 and hence counter is set to reset i.e. 000.
nand receives 000, processes it and the counter gets out from reset state.
counter produces 001 as expected.

The only change one could observe with this configuration compared to the  normal 3 bit counter is the duration for which the counter would produce the state 000.
Rest all would remain the same.
Let me know if I could help you further.


Cycle of length k with no repeated edges I need to figure out what is the minimum complexity class (L, NL, P, NPC etc..) of the following problem: Given an undirected graph G, is there exist a cycle (doesn't have to be a simple cycle) with no repeating edges, of a size at least k? (i.e. the number of edges in the cycle is at least k)

I thought that this problem can be reduced somehow to the euler cycle problem, but have no idea how to do this.

Thanks

This problem is NP-Complete.

The $\in NP$ part is simple - guess a trail and check it.

The hardness part comes from the fact Hamiltonicity on a cubic graph is hard, as proved in Garey and Johnson book.

(In a cubic graph, every vertex-simple path walk is edge-simple, as it can not visit a vertex more than once, except maybe the start and end vertex).


Summation Properties of Big Omega What are the properties of summation with Big Omega? I have been looking online but cannot find any sources on summation with Big Omega, only for Big Oh. For example, my main inquiry is if this statement is true or not, If $a(x) + b(x) ∈ \Omega(c(x))$, then $a(x) ∈ \Omega(c(x))$ or $b(x) ∈ \Omega(c(x))$.

Essentially, anything you can prove for $O(-)$ has a closely related fact that you can prove for $\Omega(-)$, in essentially the same way.  By "closely related", I mean that you might have to swap $\geq$ and $\leq$ and things like that.

You can check that the following is a counterexample to your statement about $a$, $b$ and $c$.
\begin{align*}
    a(x) &= \begin{cases}x&\text{if $x$ is even}\\0&\text{if $x$ is odd}\end{cases}\\
    b(x) &= \begin{cases}0&\text{if $x$ is even}\\x&\text{if $x$ is odd}\end{cases}\\
    c(x) &= x\,.
\end{align*}


Is it decidable whether a Turing machine modifies the tape, on a particular input? Is $L=\{\langle M,w \rangle|M\text{ does not modify the tape on input w}\}$ decidable?

We could tell if a TM does not modify the tape on any input by checking if there are no transitions in $M$ that write on the tape, but can it be decided for a given $w$?

Yes, this is decidable.  Here are two different proofs of that fact.

A counting proof

Define a configuration to be the state of the tape, the location of $M$'s head, the state that $M$'s finite control is in, and whether or not $M$ has written to the tape yet.  Note that for a fixed $w$, if $M$ does not modify the tape on input $w$, there are only finitely many possible configurations, let's say $N$ of them.  $N$ can be easily computed; it is about $2 \times (\text{len}(w) + 2|M|) \times |M|$ where $|M|$ is the number of states in $M$'s finite control.  (See footnote *.)

So, run $M$ on input $w$ and keep track of all the configurations it enters.  One of three things must happen:

After at most $N$ steps, $M$ modifies the tape.  In that case you know $\langle M,w \rangle \notin L$ and there's no need to keep simulating $M$.
After at most $N$ steps, $M$ halts without ever modifying the tape.  In that case you know $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.
After at most $N$ steps, $M$ repeats some prior configuration without ever modifying the tape and thus enters a cycle.  In that case you know $M$ will loop forever on input $w$, without modifying the tape, so $\langle M,w \rangle \in L$ and there's no need to keep simulating $M$.

Thus, after simulating $M$ for $N$ steps, we learn whether $M$ will ever modify the tape on input $w$.

Footnote *: In this proof I will consider as equivalent all configurations where the head is more than $|M|$ cells to the right of the input and that differ only in the location of $M$'s head, and I consider as equivalent all configurations where the head is more than $|M|$ cells to the left of the input and that differ only in the location of $M$'s head.  Why?  If it ever reaches one of those configurations without modifying the tape, then it will loop forever without modifying the tape.  This follows by a pigeonhole argument; the finite control can't count higher than $|M|$, i.e., if it reaches one of those configurations, then some state of the finite control must have repeated during the time when it's wholly to the right/left of the input, so it has entered a loop.

A conceptual proof

For a given $w$, if $M$ doesn't write to the tape, it is equivalent to a two-way deterministic finite automaton (2DFA).  So, you can write down a 2DFA with the following three properties:

The DFA has a single accepting state $q_a$, with a self-loop (once it accepts, it stays accepting forever).  All other states are non-accepting.
If $M$ never writes to the tape on input $w$, the behavior of the 2DFA on input $w$ is equivalent to the behavior of $M$, and the 2DFA never transitions to the special accept state $q_a$ and never accepts.
If $M$ does write to the tape on input $w$ at some point, the behavior of the 2DFA is equivalent up until the point $M$ first writes to the tape; thereafter the 2DFA follows a transition to the special accept state $q_a$ and thus accepts.

How do we build such a 2DFA?  The 2DFA is just a copy of the finite control of $M$ (which is a finite automaton), except that it moves to $q_a$ whenever $M$'s finite control would modify the tape:

If $M$'s finite control has a transition $q_i \to q_j$ when symbol $i$ is under the head $i$ and this transition doesn't write anything, then the 2DFA has the same transition.
If $M$'s finite control has a transition $q_i \to q_j$ when symbol $i$ is under the head $i$ and this transition does write to the tape, the 2DFA has a transition $q_i \to q_a$ on symbol $i$.

Now the question just becomes: given a 2DFA, does it accept on input $w$?  This is decidable, as every 2DFA is equivalent to a (possibly exponentially larger) ordinary DFA.

Comparison of proofs

Either proof suffices to show that $L$ is decidable.  The counting proof has the advantage of not requiring fancy machinery like 2DFA.  The conceptual proof shows both that $L$ is decidable and something stronger: if we restrict attention to a single fixed $M$, then the set of $w$ such that $\langle M,w \rangle \in L$ is in fact a regular language (since 2DFA are equivalent in power to DFAs).  Pretty nifty!


Distribution of resources from providers to maximum number of receivers Consider there is a city with $n$ residents who are in need of internet and there are $m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what providers are available to him. Formally let resident $i$ has list of providers $a_i$. Also each provider has a maximum number of connections he can give, that is, provider $i$ can have at max $k_i$ connections. Find the optimal way of providing internet so that the number of residents having internet is maximum.
My thoughts on the question is that this question looks like a derivative of knack-pack problem with constraints, which suggests dynamic programing but i am unable to find the states. Could anyone help me?

This problem is a case of maximum flow problem.
Suppose we are given internet providers $p_1, p_2, \cdots, p_m$ and residents $r_1, r_2, \cdots, r_n$. Consider a flow network specified as the following.

Nodes are $s,\ p_1, p_2, \cdots, p_m,\ r_1, r_2, \cdots, r_n,\ t$, where $s$ and $t$ are two extra nodes standing for the source and the sink.
There is an edge between $s$ and each $p_i$ with capacity $k_i$.
There is an edge between $p_i$ and $r_j$ with capacity 1 if $p_i$ can provide internet to $r_j$.
There is an edge between each $r_j$ and $t$ with capacity 1.

What we want is to find the maximum flow from $s$ to $t$.
There are many algorithms to solve a maximum flow problem in polynomial time. For example, Ford–Fulkerson algorithm and Dinic's algorithm are pretty popular. Source code that implement those algorithms in various programming languages can be found easily.
All those algorithm will produce an integral maximal flow, so we will not worry in case the computed maximal flow stipulates that some provider should provide 0.42 or $\frac{\sqrt2}2$ internet to some resident. You can check the integral flow theorem.


Knapsack problem with a constraint I am familiar with 0/1 knapsack problem.
But if the following constraint is imposed... how do I solve the question?

If you choose some item 'U' you won't be able to choose another item 'V'.

For example
Items are given as [Name, Weight, Value]
Items are :
A 10 20
B 50 80
C 20 30
D 30 70
E 50 50
If you choose B then you cannot choose A.
If you choose E then you cannot choose C.
If you choose D then you cannot choose A.
In the similar way the constraints are given.
Please provide me some way to solve the above problem. Any help is highly appreciated.

Standard dynamic programming approaches are likely not going to work for this problem, because the extra "this or that but not both" constraints destroy the overlapping subproblems property. So let's break out the sledgehammer.
You can easily encode this as a 0-1 integer linear programming problem and use an off-the-shelf solver. For the given example (and some maximum weight limit $W$), a suitable 0-1 ILP problem is:
maximize $20A + 80B + 30C + 70D + 50E$
subject to
$A, B, C, D, E \in \{0, 1\}$
$10A + 50B + 20C + 30D + 50E \le W$
$A + B \le 1$
$C + E \le 1$
$A + D \le 1$
Although, it is not obvious to me that an integer linear programming solver will take full advantage of the structure of the problem. So perhaps a more specialized solution may perform better in practice.


DFA drawing for binary string with substrings of minimum length 3 with at least two zeroes in each substring In trying to gain a better understanding of finite state machines, I stumbled across this idea and have been confused as to how to approach this case in terms of a DFA.

  The set of binary strings of length at least 3 where every substring
  of length 3 contains at least two 0s.

So in other words, something like 100100010 should be in the language (L) for this DFA but something like 11001010 would not be in the language.

I know that you can start off by writing/drawing smaller DFAs for the substrings that are the pattern 000, 010, 100, 001, etc, but I cannot seem to get a hold of how it should look all together.

Any help in understanding this would be appreciated.

The condition that all words have length $\geqslant 3$ makes the computation of the minimal DFA much more difficult. Thus let us first consider the language
$$
K = \{ u \in A^* \mid \text{every substring of length 3 of $u$ contains at least two $0$} \}
$$
where $A = \{0,1\}$. The forbidden patterns of the words of $K$ are $11$ and $101$, so that $K$ is the complement of the language $A^*(11 + 101)A^*$. But there is a nicer way to write $K$, using the comment of Luke Mathieson. Indeed, apart from the last two letters, every $1$ has to be followed by two $0$. This leads to the regular expression
$K = (0 + 100)^*(\varepsilon + 1 + 10)$. I let you compute the minimal DFA of $K$ which has only three states (plus a sink state if you want a complete DFA).

Now $L = A^3A^* \cap K$ and you can use standard algorithms to get its minimal DFA
(9 states, 10 if you count the sink state).


In counting sort time complexity notation O(n+k), k is number of distinct elements? Do I get right, that if we say that counting sort time complexity is O(n+k), this notation means that n is number of all elements to sort and k is number of distinct elements?

For example for array [ 3, 5, 7, 5, 1, 5]
n = 6 and
k = 4 ?

Time complexity of counting sort is $O(n + k)$ where $n$ is the size of array, and $k$ is the maximum element in the array, not the number of distinct elements.

For example if we have the array $A = \text{{1, 2, 3, 3, 3, 4, 5, 8, 8}}$ Let's say that for our array $n = 9$ because we have $9$ elements, and $k =8$ because our biggest element is $8$.

Now we create another array $B$ of size $k$ where for each number in the range $[1, k]$ we keep how many times in occurs in the array $A$. $B = \text{{1, 1, 3, 1, 1, 0, 0, 2}}$.

Now we iterate through the array $B$ and for each index $i$ in $B$ we do exactly $B[i]$ iterations. We can see that sum of all numbers in $B$ equal $n$ so we do $k$ iterations in the first for and $n$ iterations in the second for.

In total the complexity is $O(n+k)$ where $n$ is the size of array and $k$ is the biggest element in the array.