Representing partialled/curried functions in postfix notation? I'm working on a small query language in JSON. A query consists of a JSON array of JSON elements, such as strings, numbers, booleans, etc. Strings starting with a '$' or '@' represent postfix unary or binary operators, respectively.

I want to include some functional aspects to my query language (e.g. a map operator that takes a function and an array, and produces a new array). However, I'm having trouble representing these "functions-as-arguments" in postfix notation! As an example, let's say I want to add a fixed number to each element of an array. I would instinctively want to write something like this:

[[0, 2, 4, 6, 8], 1, "@add", "@map"]

However, this would be interpreted as "perform an add operation on 1 and [0, 2, 4, 6, 8], and then call map". This would produce an error in my query! Instead, I want to interpret the query as "perform a map operation using add(1) on [0, 2, 4, 6, 8]". Is it possible to achieve this, given the use of postfix notation?

The distinguishing quality of the postfix notation, a.k.a. reverse polish notation is that for its usual left-to-right evaluation strategy, just before an operator is feed from the notation, all of its operands (a.k.a as parameters or arguments) are on the top of the stack right next to each other in the expected order. Then the operator are applied to its operands immediately. The postfix notation thus has the following distinct advantages.

No operator precedence or associativity rules are needed to evaluate the notation.
Formulas can be expressed with the notation without parentheses.
The memory needed to evaluate the notation is smaller.
It is very easy to code the evaluation of the notation.

Here is one simple solution.

Instead of [[0, 2, 4, 6, 8], 1, "@add", "@map"], we will use

[[0, 2, 4, 6, 8], [1, "@add"], "@map"]

Here is how it will be processed. [0, 2, 4, 6, 8] and [1, "@add] are pushed onto the stack. When the operator "@map" is encountered, we will pop off [1, "@add"], treating it as a function object. Then with the array [0, 2, 4, 6, 8] popped off the stack, we will apply the function to the array, leaving [1, 3, 5, 7, 9] on the top of the stack.

We can simplify further.

It is quite likely that an array can be recognized conveniently and efficiently as a function object at the time when it is read as the next element of the input. For example, we should be able to detect that whether an element is an array, and if it is, check whether the last element of that array is a binary operator or not. If it is, then the array represents a function object. Otherwise, the array consists of pure data.  We can then use

[[0, 2, 4, 6, 8], [1, "@add"]]

so that we can do away with the entry "@map". Semantically, we are recognizing [1, "@add"] as a unary operator on an array without the presence of "@map". Upon applying [1, "@add"] to the array [0, 2, 4, 6, 8], we will push the result [1,3,5,7,9] to the stack. Similarly, upon processing the following JSON input,

[[0, 2, 4, 6, 8], [1, "@add"], [2, "@multiply"]],

we will leave [2, 6, 10, 14, 18] on the top of the stack.

The solution above upholds that distinguishing quality of the postfix notation. It could be extended to function objects of multiple arguments and higher order naturally and unambiguously. It can be read easily—an array of two elements whose last element is a binary operator like "@add" is a function object.

However, this solution is only one minor technique/hack to extend the primitive postfix notation. It might be helpful to study literature on postfix notation and stack-based languages for more complete and systemic usage of postfix notation. For example, check the syntax of Forth language, where new functions/words can be defined.


Why can we write almost any nonzero 2-adic integer in the same form? The title was difficult to formulate (I am open to suggestions). Two things bug me about this:

"is almost any" is imprecise, which goes against Volume 1's statement on definiteness.
When he writes, "in other words", this means Prof. Knuth explained it to me in two ways and I still do not understand it.

What is going on here in Plain English?

  If $x$ is almost any nonzero 2-adic integer, we can write its bits in
  the form  $$x = (\alpha01^a10^b)_2 $$

  in other words, $x$ consists of some arbitrary (but infinite) binary
  string of $\alpha$, followed by a $0$, which is followed by $a+1$
  ones, and followed by $b$ zeros, for some $a \geq 0$ and $b \geq 0$.
  (The exceptions occur when $x = -2^b$; then $a = \infty $)

  Consequently

  $$ \bar{x} = (\bar\alpha10^a01^b)_2 $$

  $$ x-1 = (\alpha01^a01^b)_2 $$

  $$ -x = (\bar\alpha10^a10^b)_2 $$

  and we can see that $\bar{x} +1 = -x = \overline{x-1}$, ...

  With two operations we can therefore compute relatives of $x$ in
  several useful ways:

  $x \mathbin{\&} (x-1) = (\alpha01^a00^b)_2$
  $x\mathbin{\&} -x = (0^\infty00^a10^b)_2$
  $x \mathbin{|} -x = (1^\infty11^a10^b)_2$
  $x \oplus -x = (1^\infty11^a00^b)_2$
  $x \mathbin{|} (x-1) = (\alpha 01^a11^b)_2$
  $x \oplus (x-1) = (0^\infty00^a11^b)_2$
  $\bar{x} \mathbin{\&} (x-1) = (0^\infty00^a01^b)_2$
  ...
  $((x|(x-1))+1) \mathbin{\&} x = (\alpha 00^a00^b)_2$

Knuth, Donald. The Art of Computer Programming. Volume 4, Fascicle 1. p. 8.

The pattern $x = (\alpha01^a10^b)_2$ is very easy to match. For example, the number $1=0^\infty1$ matches the pattern with $\alpha=0^\infty, a=b=0$. Try matching some other numbers yourself. The only thing this pattern asks for, is for the string "$01$" to appear somewhere in the sequence of bits. The only numbers to fail this condition are $0=0^\infty$ and $-2^b=1^\infty0^b$.


Finding no. of leaf nodes for each node in a BST A program takes as input a balanced binary search tree with $n$ leaf nodes and computes the value of a function $g(x)$ for each node $x$. If the cost of computing $g(x)$ is

$\qquad \min(\#\text{leaves in } L(x), \#\text{leaves in } R(x))$

for $L(x), R(x)$ the left resp. right subtree of $x$, then the worst-case time complexity of the program is

$\Theta(n)$
$\Theta(n \log n)$
$\Theta(n^2)$
$\Theta(n^2 \log n)$

I am actually looking for a subtle hint.

Traverse your graph in post order, create two auxiliary functions, $Cost$ and $Total$, first one demonstrates cost of your $g(x)$ at each vertex, second one calculates total number of leafs. set the cost function to zero: $Cost(leaf)=0$ for leaf, and $Total(leaf) = 1$ for leaf, then for parent node set this two functions as:

  $$Cost(v) = min\{Total(child_l),Total(child_r)\}$$$$Total(v) = Total(child_l) + Total(child_r)$$

Because is post order, will be filled correctly and is $O(n)$ algorithm.

But actually worst case complexity in different algorithm may be differ, you can show that you cannot do this better than $\Omega(n)$, and above algorithm is $\Theta(n)$, which gives a tight bound, but, may be someone implement it in a bad way that causes to the $\Omega(n^9)$, or may be someone else provide an algorithm of $\Theta(n^3)$, At all, I mean your current question is not well defined, and if it was for real exam, it was wrong, and any answer which satisfies $\Omega(n)$ barrier, is correct.


Why Is My Proof Of Asymptomatic Time Complexity Of A Dynamic Array Using The Accounting Method Getting A Wrong Answer? I had trouble formatting the summation symbols, so if anyone knows how to do it correctly feel free to edit.

I just read the asymptomatic analysis chapter from CLRS. While the aggregation and potential method are clear to me, I thought I should do some extra practice with the accounting method. My goal was to prove that if you have an array size 1, and when it fills up, you double the size, results in a time complexity of O(1) per operation. Using aggregate analysis, here is the proof I came up with:

If you call append n times, then the time complexity would be this:

$\sum_{i=1}^{\log n} \frac{1}{2^i}$

which is less than

$\sum_{i=1}^{+\infty} \frac{1}{2^i}$

which is equal to $2n$. So, the time complexity for all N operations will be O(N), so the time complexity for a single operation is O(1).

However, if the size starts at 1, then adds by 1 instead of multiplying by 2 (meaning, size starts 1, then becomes 2, then becomes 3, etc...) then the time complexity should be O(N), which I get using aggregate analysis.
$\sum_{i=1}^{n} (i+1)$

the extra 1 comes from actually placing the next element. This is equal to around (n(n + 2)) / 2, or O(N ^ 2) for all N operations, and O(N) for a single operation, which is correct. However, using the accounting method I get another answer. The actual cost of placing an element is 1, and the asymptomatic cost I set is 2. So the first time costs 2, and the second call the copying doesn't take any extra time because I prepaid it before, and the extra cost of placing that element is 2. So, it becomes:

$\sum_{i=1}^{n} 2$

which is equal to O(N) for all total operations, and O(1) for a single operation. This isn't the correct output. Where did I go wrong, and how can I fix it?

First of all notice that your first aggregate analysis should read $\sum_{i=1}^{\log n} 2^i = 2^{\log n + 1} - 2 < 2n$. (What you have written makes no sense since $\sum_{i=1}^\infty \frac{1}{2^i} \le 1$, which would mean that the aggregate complexity is upper bounded by a constant regardless of the number of operations).

Then in your last analysis you can't just place one extra credit on each element because it would only pay for the first time that such element is copied (i.e., only for the next insertion).


Master's Theorem recurrence Given recurrence relation $T(n)=8T(n/6)+n \log n$, I get that the running time of the leaves should be $n^{\log_6 8}$ and $f(n)$ should be $n \log n$, but how can I know which one is bigger ?

$n^{\log_6 8} = n^c$ for some $c>1$ (you can tell that $\log_6 8 > 1$ from the fact that $8>6$). Then $n^c = \omega(n \log n)$.
Indeed:
$$\lim_{n \to +\infty} \frac{n^c}{n \log n} = \lim_{n \to +\infty} \frac{n^{c-1}}{\log n} = \lim_{n \to +\infty} \frac{(c-1)n^{c-2}}{1/n} = \lim_{n \to +\infty} (c-1)n^{c-1} = +\infty.$$


NP completeness proof of sensor selection problem There are $n$ points in a plane.

The decision problem is to identify whether there exists a set $S$ of $k$ or less points from the $n$ points such that all $n$ points are at most $d$ distance from the selected set of points.

I am trying to use the sensor coverage problem where the idea is to place sensors in the plane where all $n$ points are reached. However, it allows the sensors to be placed at non-$n$ points which my problem doesn't allow. Is there some way I can still show that the problem is NP-complete by subset selection or any other approach.

Thanks!

Your problem is an instance of a geometric cover problem.  Specifically, it appears to be very close to the discrete unit disc cover problem (just scale down all distances by a factor of $d$), which is apparently NP-hard but also admits reasonable approximation algorithms.


Soft Margin Loss and Conditional Probabilities Consider the following soft margin loss function: $\max(0, 1-yf(x))$.  I have the problem of needing to compute the conditional probability $p(y|x)$ corresponding to this function and am having trouble making the connection between conditional probability and this function.  I have come across a few papers (e.g. http://www.unc.edu/~yfliu/papers/lum.pdf) that say that "soft classifiers explicitly calculate the class conditional probabilities", but I do not understand how as the output of a classifier is not a probability.  Can someone please explain what I am missing?

It is not possible to consistently estimate $P(y \mid x)$ if you are learning with hinge loss. Strictly proper losses, also known as strictly proper scoring rules, are the subclass of loss functions that are consistent for probability estimation. There is now a comprehensive and rich theory of proper losses, the larger class containing strictly proper losses. Without getting far into the theory of these losses, I'll give some examples/non-examples and some properties that strictly proper losses have.

The following are strictly proper losses: squared loss (least squares), log loss (logistic regression), exponential loss (boosting). The following are not strictly proper nor even proper losses: absolute loss, hinge loss (SVM).

One reason proper losses are so important is that if a loss is proper, then it is possible to map the edge $y f(x)$ to a class probability in a consistent way (if we ignore regularization). This can be done by appealing to a link function corresponding to the proper loss. In the binary classification setting, a link function maps from the interval $[0, 1]$ to the "edge space" inhabited by $y f(x)$. Given an edge $y f(x)$, the inverse link can be used to get a probability. For strictly proper margin losses (any of the strictly proper losses listed above), you can get the link function from Corollary 14 of this paper: http://jmlr.org/papers/volume11/reid10a/reid10a.pdf. This paper also discusses the problem with hinge loss for class probability estimation.

Briefly, the problem with absolute loss and hinge loss are that if a learning algorithm believes $P(Y = 1 \mid X = x) > 0.5$, then both these losses are minimized by maximizing the edge $y f(x)$. In contrast, for squared loss and other strictly proper losses, the loss is minimized when the edge (after passing it through the inverse link function) corresponds to Learner's believed $P(Y = 1 \mid X = x)$.


number of pair of vertices with at least 2 distinct paths between them in a undirected graph I need an algorithm to calculate number of pair of vertices with at least 2 distinct paths between them in a undirected graph
- the graph is connected
- distinct paths = distinct edges
ex:
no. of vert = 3 and no. of edges = 3
and we have (1, 3) (1, 2) and (2, 3)
valid paths from 1 to 2 are 1-3-2 and 1-2
- count only pairs (a,b) with a < b
for example :

  5(no. of vert) 6(no. of edges) : (1, 2) (2, 3) (3, 1) (3, 4) (4, 5)
  (5, 4).

Output is 4 :

  (1, 2), (1, 3), (2, 3) and (4, 5).

I'm assuming that you're looking for the number of pairs of vertices having two disjoint simple paths connected them. A pair of vertices has two disjoint simple paths connecting them if they are in the same biconnected component. You can partition the graph into biconnected components in linear time. If the biconnected components have sizes $N_i$, then the number of pairs is $\sum_i \binom{N_i}{2}$.


Domain theory: Definition of isomorphisms Consider the following definitions of CPOs, monotonicity and continuity:
The pair $(M, \leq)$ is called CPO (complete partial order), if

$M$ is a set,
$\leq$ is a partial order on $M$,
there exists a least element according to $\leq$ in $M$ (called bottom, $\bot$),
for every chain $m_0, m_1, m_2, \dots$ in $M$ its supremum $\bigsqcup \{m_0, m_1, m_2, \dots\}$ (least upper bound) exists in $M$.

(where a chain is a sequence $m_0, m_1, m_2, \dots$ of elements in $M$ such that for all $i, j \in \mathbb{N}$ $m_i \leq m_j \vee m_j \leq m_i$ holds)

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called monotone if for all $a, b \in M$

$$a \leq b \implies f(a) \sqsubseteq f(b)$$

holds.

A function $f \colon M \to N$ between two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ is called continuous, if it is already monotone and for all chains $m_0, m_1, m_2, \dots$ we have

$$f\left(\bigsqcup \{m_0, m_1, m_2, \dots\}\right) = \bigsqcup \{f(m_0), f(m_1), f(m_2), \dots\}.$$

I read in a book using above definitions that two CPOs $(M, \leq)$ and $(N, \sqsubseteq)$ are isomorphic if there exists a function $f \colon M \to N$ such that

$f$ is bijective
$f$ and $f^{-1}$ are continuous (and therefore monotone).

I understand the demand of $f$ and $f^{-1}$ being monotone, so that they preserve the order.

Question:
Why is this not sufficient? Why do we also demand $f$ to be continuous? Why its inverse function too? What are examples where a violation of one property would result in a strange view of equivalence?
Another question: Is it possible to drop one property, because the other would imply it? I'm thinking about to demand only $f$'s continuity and to show that $f^{-1}$'s continuity follows – however I was not able to do so, or to come up with a counter example.

Edit: I suggest a »domain theory« tag.

I think I have found an answer to my question, by proofing that the monotonicity of $f$ and $f^{-1}$ imply the continuity of $f$ and $f^{-1}$.
Please correct me if I made a mistake – I will give you some days to check my proof before I accept my own answer.

Lemma: If a function $f \colon M \to N$ between two cpos is monotonic, the inequality

$$\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\} \leq f\left(\bigsqcup\{ m_0, m_1, m_2, \dots\}\right)$$

holds for all chains $m_0, m_1, m_2, \dots$. This is well known and easy to show, so I will skip the proof of this.

Let $f \colon M \to N$ be now a bijective function between two cpos and let it, and its inverse $f^{-1}$, be monotonic.
By the above lemma we have already one side of inequality to proof the continuity of $f$. It remains to show that

$$f\left(\bigsqcup\{ m_0, m_1, m_2, \dots\}\right) \leq \bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}$$

holds for all chains $m_0, m_1, m_2, \dots$ in $M$.
Since $$\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\} = f\left(f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right)\right),$$

and both $f$ and $f^{-1}$ are monotonic, the above inequality is equivalent to

$$\bigsqcup\{ m_0, m_1, m_2, \dots\} \leq f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right).$$

However, again by above lemma we have

$$ f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right)
\geq \bigsqcup\{f^{-1}(f(m_0)), f^{-1}(f(m_1)), f^{-1}(f(m_2)), \dots\}
= \bigsqcup\{ m_0, m_1, m_2, \dots\}.$$

So $f$ is continuous. You show the continuity of $f^{-1}$ in the same way.


Applying dynamic programming to a simple two-person game of perfect information A natural number n represents the initial position in the game. When it is a players turn he/she is allowed to

I)  Subtract 2 from n
II) Subtract 3 from n
III)    Subtract 5 from n

We call the player who begin the game Adam and the other player Berta. The players alternate by applying on of the three rules to the number 0 or a negative number his/her opponent. If a player manages to produce the number 0 or a negative number he/she wins the game.

Here is an example of a game played by Adam and Berta (for n=15)

15 is given to Adam. He decides to subtract 5 leaving 15-5 = 10 to Berta
10 is given to Berta. She decides to subtract 3 leaving 11-3=8 to Beta
8 is given to Adam. He decides to subtract 2 leaving 8-2=6 to Berta
6 is given to Berta. She decides to subtract 2 leaving 6-2=4 to Adam
4 is given to Adam. He decides to subtract 5 producing -1 a negative number, Adam wins!

b) we define a one dimensional array X(1), X(2),X(3),..,X(n)

i)  X(j) =1 if Adam has a method to win when given the number j
ii) X(j)=0 if Adam has no method that guarantees that he wins when the given the number k

Calculate X(1),X(2),X(3)….,X(23),X(25)

What is X(8), X(13) and X(24)?     Answer should be of the form
boolean boolean boolean  so if X(8)=0 , X(13)=1 and X(24)=1 the correct answer is 011
Thus the correct answer is one of the following 000 001 010 011 100 101 110 111

My attempt is

n=8
Adam: 8-5=3
Berta: 3-3 =0
Berta wins  0

n=13
Adam=13-5=8
Berta: 8-3=5
Adam 5- 5
Adam wins 1

I get really stuck with 24, so far I have 01

Is there a method for this type of problem, i have been stuck on it for ages now.
Thanks in advance

Since you want to calculate $X(1), X(2), X(3)$,... and not just some $X(i)$, you can start from $X(1)$. Let's denote the case where there is a winning strategy for first player by $1$ and the other case by $0$.

Clearly, value of $X(i)$ for $i \in \{1,2,3,4,5\}$ is $1$. Let's store the values of $X(i)$ that we computed in an array. For $i>5$, if at least one of the values of $X(i-2), X(i-3), X(i-5)$ is $0$, then the value of $X(i)$ will be $1$. If none of them is $0$, then the value of $X(i)$ will be $0$.


Why are weights of Neural Networks initialized with random numbers? Why are neural networks initial weights initialized as random numbers?
I had read somewhere that this is done to "break the symmetry" and this makes the neural network learn faster.
How does breaking the symmetry make it learn faster?

Would'nt initializing the weights to 0 be a better idea? That way the weights would be able to find their values (whether positive or negative)  faster?

Is there some other underlying philosophy behind randomizing the weights apart from hoping that they would be near their optimum values when initialized?

The basic intuition behind initializing weight layers into small (and different) values is just so that the bias of the system is broken and weight values can move along and away and apart to different values.

More concretely, you'ld probably want your initial weights to be distinct and have "a small gap" between them, this 'gap' expands out as you go along and forces the weights to be a bit larger at every iteration, and this helps the network to converge faster, i.e. the learning process speeds up.

If you would instead have all your weights to some constant, each weight will be updated at a very slow (~fixed) rate, and this won't help much, specially if the initial values are 'very far' from the final values.

Hope that helps,
Have fun learning :)


Prove or disprove those languages are regular in my practice for a test I came across this question:
prove or disprove that those languages are regular:

I succeeded proving that the second language is nonregular with homomorphism but i'm having trouble with the other 2 -

my intuition tellin me that first 1 is Σ∗ but i'm really stuck on how to prove it
(not sure why it writes 2 when i'm writin 3 haha) in this one i'm really stuck - my intuition is tellin me again that it will be finite automaton (automata? sorry if my english is not so good) and therefore regular language but how can I prove it? how can I use the fact that |w| is bounded? - i guess I need to build an automaton , maybe with some "flags" but I suck at it (for now) :[.

does ww^R is regular language when |w| is bounded? I've looked a lot (through google in this site) for an answer for this question but I havent find something - only that this language is not regular when |w| is not bounded.

Can I get some hints on both of those languages please?

For number 1, you're entirely correct. Every string in $\Sigma *$ is in this language. Take an arbitrary string of zeroes, ones, and twos, then let $y$ be that string, and $w$ be empty.

For number 2, the standard way I learned to prove it's not regular is with "fooling sets". The Pumping Lemma also works here.

For number 3, consider that there are only finitely many possibilities for $w$. This means you could, in theory, write a regular expression that just listed all of them. So this one is actually regular, through "brute force".


Are the Before and After sets for context-free grammars always context-free? Let $G$ be a context-free grammar. A string of terminals and nonterminals of $G$ is said to be a sentential form of $G$ if you can obtain it by applying productions of $G$ zero or more times to the start symbol of $S$. Let $\operatorname{SF}(G)$ be the set of sentential forms of $G$.

Let $\alpha \in \operatorname{SF}(G)$ and let $\beta$ be a substring of $\alpha$ - we call $\beta$ a fragment of $\operatorname{SF}(G)$. Now let

$\operatorname{Before}(\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in \operatorname{SF}(G) \}$

and

$\operatorname{After}(\beta) = \{ \delta \ |\ \exists \gamma . \gamma \beta \delta \in \operatorname{SF}(G) \}$.

  Are $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ context-free languages? What if $G$ is unambiguous? If $G$ is unambiguous, are $\operatorname{Before}(\beta)$ and $\operatorname{After}(\beta)$ also describable by an unambiguous context-free language?

This is a followup to my earlier question, after an earlier attempt to make my question easier to answer failed. A negative answer will make the encompassing question I'm working on very hard to answer.

Yes, $\mbox{Before}(\beta)$ and $\mbox{After}(\beta)$ are context-free languages.  Here's how I would prove it.  First, a lemma (which is the crux).  If $L$ is CF then:

$\mbox{Before}(L,\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in L \}$

and

$\mbox{After}(L,\beta) = \{ \gamma \ |\ \exists \delta . \delta \beta \gamma \in L \}$

are CF.

Proof?  For $\mbox{Before}(L,\beta)$ construct a non-deterministic finite-state transducer $T_{\beta}$ that scans a string, outputting every input symbol it sees and simultaneously searches non-deterministically for $\beta$.  Whenever $T_{\beta}$ sees the first symbol of $\beta$ it forks non-deterministically and ceases outputting symbols until either it finishes seeing $\beta$ or it sees sees a symbol that deviates from $\beta$, stopping in either case. If $T_{\beta}$ sees $\beta$ in full, it accepts upon stopping, which is the only way it accepts.  If it sees a deviation from $\beta$, it rejects.

The lemma can be jiggered to handle cases where $\beta$ could overlap with itself (like $abab$ -- keep looking for $\beta$ even while in the midst of scanning for a prior $\beta$) or appears multiple times (actually, the original non-determinisic forking already handles that).

It's fairly clear that $T_\beta(L) = \mbox{Before}(L,\beta)$, and since the CFLs are closed under finite-state transduction, $\mbox{Before}(L,\beta)$ is therefore CF.

A similar argument goes for $\mbox{After}(L,\beta)$, or it could be done with string reversals from $\mbox{Before}(L,\beta)$ , CFLs also being closed under reversal:

$\mbox{After}(L,\beta) = \mbox{rev}(\mbox{Before}(\mbox{rev}(L),\mbox{rev}(\beta)))$

Actually, now that I see the reversal argument, it would be even easier to start with $\mbox{After}(L,\beta)$, since the transducer for that is simpler to describe and verify -- it outputs the empty string while looking for a $\beta$. When it finds $\beta$ it forks non-deterministically, one fork continuing to look for further copies of $\beta$, the other fork copying all subsequent characters verbatim from input to output, accepting all the while.

What remains is to make this work for sentential forms as well as CFLs.  But that is pretty straightforward, since the language of sentential forms of a CFG is itself a CFL.  You can show that by replacing every non-terminal $X$ throughout $G$ by say $X^\prime$, declaring $X$ to be a terminal, and adding all productions $X^\prime \rightarrow X$ to the grammar.

I'll have to think about your question on unambiguity.


Mother vertex of a graph I am trying to find all mother vertex in a directed graph.

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

My Approach:

Do DFS on each vertex and check if all the vertex are reached on each start node.
Time complexity : O(V*(V+E)).

I am looking for any better solutions with better complexity.

Any help would be appreciated.

Find the strongly connected components. If the component graph has more than one source, then there are no mother vertices. Otherwise, the mother vertices are those that belong to the single source.


Undecidability of whether a given TM halts or only has loops which can be detected by some TM This might be a bit of an abstruse question, but it's something I've been trying to prove.

I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all Turing Machines that either always halt, or have non-halting loops where all of which can be detected (a positive decision made on it's existence) by some Turing Mahcine.

I'm trying to do a reduction from the Entscheidungsproblem, and my proof looks something like this:

Create a Turing machine $D$ on input $<M,w>$ that does the following:

Mechanically create TM $M_2$ which does the following on $x$:

if $M$ accepts $w$ (via simulation from UTM): accept $x$.
if $M$ rejects $w$: loop in a manner such that $M_2$ would not be a member of the aforementioned set.

Run decider for above problem on $M_2$:

if decider accepts, it should accept because if $M$ accepts $w$, $M_2$ must always halt and must be a member of the set in question.
if decider rejects, it should reject because if $M$ does not accept $w$, $M_2$ must have a non mechanically detectable loop and is not in the set.

The above Turing Machine $D$ should therefore decide Entscheidungsproblem and shows the reduction. However, I'm not sure how to show that it possible to mechanically create a loop which cannot be mechanically detected, or whether an alternate method of proof would be adequate.

Any insight in this proof would be appreciated.

(too long for a comment)

Here's my attempt at an unambiguous version of what you are trying to get across.

  Is it the case that for every total Turing machine M,

  if[
  for all $\langle d,n\rangle$ in $\{0,1,2,3,...\}^2$, $\:$ if M accepts $\langle d,n\rangle$ then

  $d$ describes a Turing machine that enters a loop on input $n$,
  ]then[
  there is a many-one reduction from the Halting Problem

  to the set of $d$ in $\{0,1,2,3,...\}$ such that
  [
  $\hspace{.01 in}d$ describes a total Turing machine or $\big[\big[$for all $n$ in $\{0,1,2,3,...\}$,

  if $d$ enters a loop on input $n$ then M accepts $\langle d,n\rangle\big]$ and there exists such an $n\big]$
  ]?


graphs - finding a shortest path length not achievable by breadth first search supposedly for some graphs there exists valid shortest path lengths between two nodes of the graph that cant be constructed by breadth first search. what defines these shortest paths that breadth first search cant reach?

BFS doesn't work well on graphs with weighted edges, or in other words, graphs where the cost to travel each edge isn't equal. The reason for this is that BFS implicitly assumes equal path lengths. At each step, all nodes adjacent to the current node get pushed into the queue, regardless of the edge weights. This results in a situation where the number of edges traveled, rather than any actual edge weights, reflects the "path length".

For example, consider a graph with 3 nodes A, B, and C; the edge from A to B AB's weight is 2, BC's weight is 3, and AC's weight is 100. Since A is 2 edges (AB, BC) away from C by taking the path through B, but only 1 edge away from C by taking edge AC, BFS would choose AC as the "shortest path" even though it's weight is significantly higher than the sum of AB and BC.

Instead, try algorithms such as Dijkstra's and Bellman-Ford that explicitly take into account the edge weights (e.g. with a priority queue in Dijkstra's). They tend to have a greater time complexity, but will return the correct answer.


The theory behind backpropogation, gradient calculation I am reading a book about Neural Networks, that explains the backpropagation algorithm. It explains that the error function is the sum of error of all inputs, and that the algorithm minimizes this sum, which makes perfect sense to me, but than in goes on stating that to achieve that the gradient is calculated for each input, and then summed up. This last step is not understable to me.

Is it implying that the gradient of the sum of all errors (from all inputs) is equal to sum of gradients (from all inputs), that is - that the sum of gradients equals the gradient of sum?

This seems to me like an non trivial step, but it is not explained in the book.

The gradient, just like the derivative, is linear: for functions $f,g$ on the same variables and scalars $\alpha,\beta$:
$$
\nabla(\alpha f + \beta g) = \alpha \nabla f + \beta \nabla g.
$$


Turing Machine equivalence in MinTM proof The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows:

  $C=$ "On input $w$:

  Obtain, via the recursion theorem, own description $\langle C \rangle$.
  Run the enumerator $E$ until a machine $D$ appears with a longer description than that of $C$.
  Simulate $D$ on input $w$."

$MIN_{\mathrm{TM}}$ is infinite, so at least one $D$ occurence will be observed.

Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal.

I would like to understand three things from this proof:

How do we know that $MIN_{\mathrm{TM}}$ is inifinite?
Why $C$ is equivalent to $D$?
Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$ cannot be minimal"?. Why do we expect $D$ to be minimal?

Edit :
I have some opinions (I want to verify) about my questions. Please correct me If I am wrong.

Equivalence is based only on ability to construct same language recognizers
or to say $L(M_1) = L(M_2)$

How do we know that $MIN_{\mathrm{TM}}$ is inifinite?

There are infinitely many partial recursive functions (i.e., functions which are computed by TMs) and to each such function there is at least one TM which computes it and has minimal description.

  Why $C$ is equivalent to $D$?

Because of point 3., which essentially forces $C$ and $D$ to have the same behavior. In this case, yes, equivalence is used in the sense that $L(C) = L(D)$.

  Why "Because $C$ is shorter than $D$ and is equivalent to it, $D$
  cannot be minimal"?. Why do we expect $D$ to be minimal?

$D$ is minimal because $\langle D \rangle \in MIN_{\textrm{TM}}$. Recall that, by assumption, the enumerator $E$ only outputs descriptions in $MIN_{\textrm{TM}}$. The point is that $\langle C \rangle$ is fixed (because we have just provided a description for it), but $E$ gives us descriptions of TMs of arbitrary length indefinitely; hence, $E$ will eventually output some description which is longer than $\langle C \rangle$.


Are any problems in P known to have logarithmic-time-verifiable certificates? Problems in NP have certificates which can be verified in polynomial time.

It seems conceivable that there could be problems in P which have certificates which can be verified in logarithmic time.  (Such certificates would also have to be logarithmic in size, naturally.)

However, it is also conceivable that there are no such problems.  I've tried to come up with examples, but none of them have worked out so far.

Have problems like this been studied and shown to exist (or not exist)?

I can't seem to find a complexity class that would describe them in the Complexity Zoo, although it's certainly possible that there's one there and I'm just having a hard time identifying it.  (L and LOG usually refer to space, and neither LH nor NLOG looks like it necessarily captures the idea.)

The question here is that in the certificate definition of $\mathsf{NP}$, what is more important is the size of the certificate (in the size of the input), the complexity class that  the certificate verifier belongs too is less important. In fact you can take the verifier to be in $\mathsf{AC^0}$ as long as the size of the certificates are polynomial in the size of the input and you will still get the whole problems in $\mathsf{NP}$. $\mathsf{AC^0}$ is a very small complexity class that is included in almost every complexity class you have heard of.

To obtain smaller classes you also need to restrict the way the certificate verifier accesses the certificate. One kind of restriction that is considered is restricting the number of times  the verifier can read the input using a log-space verifier. Something similar may work to capture $\mathsf{P}$, but just capturing it in this way is not interesting. The certificate definition should be nice and interesting so that it would give us some insight about $\mathsf{P}$. The certificate definition of $\mathsf{NP}$ is interesting because it is an exceptionally nice, it is even more intuitive than the original definition using non-intuitive non-deterministic machines. It allows us to cast the question regarding $\mathsf{P}$ vs. $\mathsf{NP}$ as "efficient solving vs. efficient verifying". Just having a certificate definition by itself is not very interesting.


Random sampling of tuples When I talked with students about pseudo-random number generation, I mentioned that you should not blindly use subsequent outputs of a pseudo-random number generator (PRNG) to form tuples as they may not be uniformly random then; a famous example is RANDU.

The natural follow-up question is: what do you do? I can imagine several strategies.

Choose a PRNG that you know works well for $k$-tuples and sample $(\leq k)$-tuples by using subsequent numbers as components.

I assume that $k \leq 5$ is probably covered, but are there any for arbitrary $k$?
Use $k$ different PRNGs (different algorithms and/or different seeds) and
draw the $i$th component from the $i$th one.

I seem to remember that mixing PRNGs is not a good idea.
If the domain of your PRNG is big enough, use bits $i,k+i,2k+i, \dots$ for the $i$th component.

Seems sound and is probably the method of choice assumign real $U(0,1)$-numbers, but does not scale given finite resolution/domains in practice.
Use a bijection from the domain of your PRNG to the $k$-dimensional space you want to sample from, e.g. a generalized version of Cantor's pairing function.

The sizes of the resp. domains can become a problem here a well.

None of the approaches seems entirely reasonable. So what is the state of the art? What advice would you give a person who needs to sample uniformly random tuples?

Using consecutive outputs from the PRNG to form a tuple is fine if you use a good enough PRNG.  So, one reasonable approach is to simply use a good PRNG, and then not waste brain power worrying about issues like this.

One way to get a "good enough" PRNG is to use a cryptographic-quality PRNG.

RANDU is a truly lousy PRNG (for instance, the least significant bit of its output is not random at all), so no surprise that all sorts of bad things happen when you use its output.  But the root cause there is not using tuples from RANDU; the root cause is using RANDU.


Does types being terms imply your dependend theory is considered polymorphic? In the introduction of the book by B.Jacobs, "Categorical Logic and Type Theory" (it's online here), he classifies type systems into three general flavours: Simply typed ones, depended typed (term depended types) and polymorphic types (type depended types). He says also there are also mix types.

Now if you start out with a dependently types theory and introduce transitive universes, hence forcing types on the level of terms, are you automatically speaking of a polymorphic type system then?

These three “flavors” are usually presented as the lambda cube. They aren't really flavors but properties that can be combined independently, so there are not $3$ but $2^3 = 8$ flavors. In fact you could go as high as $4$ properties yielding $16$ flavors:

terms depending on terms, i.e. functional languages (e.g. $f : x \mapsto x+2$);
terms depending on types, i.e. polymorphism (e.g. $\mathrm{head} : [X] \rightarrow X$);
types depending on types, i.e. type operators (e.g. $\mathrm{list} : X \mapsto [X]$);
types depending on terms, i.e. dependent types (e.g. $\mathrm{array(int)} : n \mapsto \mathrm{int}^n$).

Theories without lambda abstraction tend to be less interesting and do a bad job of encoding most programming languages, so they're generally left out.

If you introduce transitive universes, then having types depending on terms automatically gives you types depending on higher-order terms, i.e. types. The Barendregt cube tends to collapse when terms and types are collapsed. However this doesn't necessarily give you all the polymorphism you want. The Barendregt cube is a classification; it doesn't reflect all the properties of the language. In particular, polymorphism can be more or less explicit, requiring you to thread type arguments down to every function, or not.

I think the right way to put it is that you're automatically speaking of a type system that can encode a polymorphic type system, but not necessarily give it to you the way you want.


How do we know that the reduction is correct? I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable.

Here's my reasoning:

Let's say that we want to find out if the following problem is decidable: given any machine $M$ and a string $y$ find out whether the machine $M$ ever writes an $@$ symbol on the tape.

So, I intuitively think that this is an undecidable problem and I try to reduce the halting problem to our problem.

Let's have an arbitrary machine $N$ and a string $x$. If $N\#x \in HP$ then $N$ halts on input $x$ else if $N\#x \not\in HP$ then $N$ loops on input $x$ where $HP = \{ M\#x\ |\ M\ \text{halts on}\ x\}$.

Here's my first question: how do we know if $N\#x$ belongs to $HP$ or not? I thought that we cannot tell and that's the whole idea behind the halting problem.
Now we typically construct a machine $M'$ which has $N\#x$ hardcoded inside and which output doesn't depend on its input. Here's how $M'$ works:

Erase the input.
Run $N$ on $x$.
If $N$ halts on $x$ then have $M'$ write $@$ to the tape. Otherwise, if $N$ loops on $x$ then have $M'$ make sure $@$ is not written on the tape.

From what I understand, the proof is over as the behaviour of $M'$ is similar to $HP$ (I am not sure if this is the correct way to formulate this) and since the halting problem is undecidable then our problem is undecidable as well.

Here comes my second question: why does it prove anything? It looks like any problem could be treated this way leading us to the conclusion that everything is undecidable as we were able to incorporate the halting problem in our algorithm. How do I know that there is no way to avoid an undecidable problem in my algorithm? I feel like we're showing that we can use the halting problem to solve my problem instead of showing that solving my problem would result in solving the halting problem as well.

I'm sorry if my explanation is a little bit vague – I've already consulted my professor, read related chapters in Automata and Computability by Kozen and tried to read tutorials and presentations on the Internet but I still cannot understand the logic behind the reduction. I'd be grateful if someone could explain my misunderstanding.

Your first question is easy to answer: you are confusing "we know" with "it is the case". It can happen that something is the case but we do not know it. In particular, it is the case that $M\#x$ halts or it does not halt, but we do not know which. It will rain a year from now or not, but we do not know which.

To answer the second question, let us see what goes wrong if we try to reduce the Halting Problem to a decidable problem. Consider the problem:

  Given a single-tape Turing machine $M$ and input $x$, decide whether $M\#x$ halts in fewer than $\mathrm{length}(x)$ steps.

Now we need to come up with a reduction, i.e., given any machine $M$ and input $x$, we must produce a machine $M'$ and input $x'$, such that
$$\text{$M$ halts on $x$} \iff \text{$M'\#x'$ halts in fewer than $\mathrm{length}(x')$ steps}$$
Here is an idea: let $x'$ be the pair $(x, 0^k)$ where $0^k$ is a a string of $k$ zeroes, where we are going to determine $k$ later (this trick is know as "padding the input"). The machine $M'$ takes this input $(x, 0^k)$, ignores $0^k$ and just does whatever $M\#x$ would do. Now, for this reduction to work, we just need $k$ such that
$$\text{$M\#x$ halts} \iff \text{$M'\#(x,0^k)$ takes fewer than $\mathrm{length}(x,0^k)$ steps of execution}$$
Such a $k$ exists because $M\#x$ halts if, and only if, $M'\#(x,0^k)$ halts. So there are two cases:

If $M\#x$ halts then so does $M'\#(x,0^k)$ in some number of steps, say $m$, and we can take $k = m + 1$.
If $M\#x$ does not halt then we can take any $k$.

There is a small technical issue: the number $m$ should not depend on $k$. We can arrange this in several ways. One possibility is to allow $M'$ to have an extra symbol which it uses as "ignore input from here onwards". In any case, this is not essential for the discussion at hand.

Can you spot the problem? A reduction needs to be computable, that is, we need a computable procedure which generates $M'$ and $x'$ from $M$ and $x$. We have not given a procedure for computing $k$, even though such a $k$ exists. Perhaps if we think harder we can come up with the required procedure for computing $k$. Or perhaps it does not exist, and our attempt is not worth anything. We just do not know.

So, this is one way in which an attempt at a reduction may fail. It is in fact typical: if we are allowed to use non-computable reductions, then we can reduce any problem to any other non-trivial problem. I leave it as an exercise. (Here "non-trivial" means that the problem has an instance where the answer is "yes" and an instance where the answer is "no".)


Self-reducibility of Clique I am trying to understand the following algorithm for Self reducibility of Clique.

Here we have a "MBClique" black box algorithm, which return yes/no for parameters  where G is a graph and K is a natural number. It answers the question: "Does G has a clique of K size?" - Our aim is then to use this Decision algorithm to search what the actual Clique graph is.

Given this Graph below, we can see it has a clique of size 3.

The search algorithm is as follows (it was extracted from the CSE 200: Computability and Complexity @ UCSD lecture notes, page 4):

Ok, so now given an algorithm MBClique that returns yes/no we are trying to search the actual k-clique. Suppose the graph of the image above is sent as parameter and k=3.

In the first if it passes through.
In the immediate after For loop all edges that don't affect the size of the clique are removed.
Now my question: what is the Repeat...Until part of the algorithm for? In my understanding after the For loop I already have the respective Graph that I want as an answer.

Thanks.

The Repeat loop is not strictly necessary.  The algorithm would still be correct without it.  In fact, the Repeat loop actually has no effect, though proving this takes a little bit of work.

If the graph $G$ has no $K$-clique, then this procedure correctly halts.  So assume the graph $G$ has at least one $K$-clique.  The interesting case is where it has multiple $K$-cliques.

Associate each $K$-clique with a vector $(x_1,x_2,\dots,x_K)$ representing the vertices of the clique, in increasing order.  Now order these cliques by lexicographic order on the vectors.  Let's focus on the $K$-clique whose corresponding vector is lexicographically largest; call this the "golden" $K$-clique.  It is possible to prove that For loop removes everything but the "golden" $K$-clique: when the For loop terminates, all that remains is a subgraph containing exactly $K$ vertices, namely, the golden $K$-clique.  Therefore, the Repeat loop does nothing.

In other words, you can remove the Repeat loop, and this procedure will always produce the same output.  (In particular, you were worired that the Repeat loop might remove a vertex from an actual clique -- but the above reasoning shows that this can never happen.)

So, the Repeat loop is unnecessary.  Why is it there?  Maybe to make the proof of correctness for this algorithm a bit easier.  But if you find the algorithm easier to understand if you omit the Repeat loop, go ahead and pretend it's been removed -- that will work, too.


Are $\mathsf{\#P}$ problems harder than $\mathsf{NP}$ problems I have a method to solve the $\mathsf{\#P}$ version of 3SAT in a way that seemingly reduces it to an $\mathsf{NP}$ problem. - I don't have a formal understanding of these terms so I will just show an example here.

  How many solutions does $\phi=\left(x_1 \vee x_2 \right) \wedge
 \left(\neg x_1 \vee x_3 \right) \wedge \left(\neg x_2 \vee \neg x_3
 \right)$ have?

First convert to a boolean polynomial:
$$\phi=\left(x_1 + x_2 -x_1x_2\right) \left(1-x_1+x_1x_3\right) \left(1-x_2x_3 \right)$$

Expand and simplify (using, e.g., $x^2=x$ for Boolean values):
$$\phi = x_2 - x_1x_2 + x_1x_3 - x_2x_3$$

Substitute $x_1 = x_2 = x_3 = \frac{1}{2}$ and multiply by $2^n$ where $n$ is the number of variables:
$$|\phi| = 2^n\left(\frac{1}{2} - \frac{1}{4} + \frac{1}{4} - \frac{1}{4}\right) = 2^3\frac{1}{4} = 2$$

where $|\phi|$ is the number of solutions that $\phi$ has.

And indeed, those 2 solutions are $(0,1,0)$ and $(1,0,1)$.

I have proven that this works for any logical expression. Does this have any use/bearing on  $\mathsf{\#P}$ vs $\mathsf{NP}$?

As I have hinted at in the comments, that your reduction exists is not at all surprising. As in my answer to your previous question, your "Expand and simplify" part takes potentially exponential time and, thus, does not qualify as a polynomial-time reduction (which is the standard notion used to compare the classes in question). Exponential-time reductions here are irrelevant because both $\mathsf{NP}$ and $\#\mathsf{P}$ are contained in $\mathsf{EXP}$, so the reduction is powerful enough to solve the problems it should be reducing.

As to address the question in the title, notice the following: Let $P \in \mathsf{NP}$ be some problem, $S_P$ the solution set associated with $P$ (i.e., the $\{0,1\}^\ast \times \{0,1\}^\ast$ relation which, for instance, associates each $x \in P$ with its (poly-time verifiable) solutions), and $\#S_P\colon \{0,1\}^\ast \to \mathbb{N}_0$ be the counting problem associated with $S_P$, that is, $\#S_P(x) = |S_P(x)|$. For $P = \mathsf{SAT}$, for example, $S_P$ is simply the relation of formulas to their satisfiable assignments, and $\#S_P$ the number of satisfiable assigments. Then you can recast $P$ as the (decision) problem $\{ x \mid \#S_P(x) \ge 1 \}$. This means that having a procedure which counts solutions (i.e., computes $\#S_P \in \# \mathsf{P}$) directly yields something which decides $P \in \mathsf{NP}$.

Not only that, but notice that above we do not even actually use the value $\#S_P(x)$ other than to test that it is not zero. It is conceivable that we can use that accurate value towards solving problems much harder than $\mathsf{NP}$ (e.g., as Toda's theorem tells us; see David Richerby's answer). This gives us enough reason to believe that problems in $\#\mathsf{P}$ are, in general, much harder than those in $\mathsf{NP}$ (the most conspicuous candidates being the $\#\mathsf{P}$-complete problems).


Number of edges in a graph with N vertices and K components What is the possible biggest and the smallest number of edges in a graph with N vertices and K components?

I think that the smallest is (N-1)K. The biggest one is NK. Is this correct? I think it also may depend on whether we have and even or an odd number of vertices?

Think of the extreme case when all the components of the graph except one have just one vertex. This is the case which will have the most no. of edges. We can prove it by contradiction as follows:Suppose there were two strongly connected components having $m$ and $n$ vertices where $m < n$. Now if you remove a vertex from the one having $m$ vertices and add it to the other component, then effectively you have removed $m-1$ edges from the first graph and added $n $ edges to the second graph. So, there is a net gain in the number of edges. So the maximum edges in this case will be $\dfrac{(n-k)(n-k+1)}{2}$.As for the minimum case, since we have seen that distributing the edges with uniformity among the graphs leads to an overall minimization in their number, therefore first divide all the $n$ vertices into $k$ components to get the number of vertices in each component as $n/k$. We will still be left with  $n\mod k = f'$  vertices. Let's call $\Biggl\lfloor{\dfrac{n}{k}}\Biggr\rfloor$ = $f$. Then, the $k$ components each already have $f$ vertices with them. Now , give away $1$ vertex each to first $f'$ components. This completes our vertex distribution. So, total edges$ = (f + 1 - 1)*f' + (f-1)*(f - f')$ (because we have minimum of $x-1$ edges for $x$ available vertices) where the first term counts minimum edges for first $f'$ components which have 1 vertex extra and the second term is for the remaining components.


Complexity of finding factors of a number I have come up with two simple methods for finding all the factors of a number $n$. The first is trial division:

For every integer up to $\sqrt{n}$, try to divide by $d$, and if the remainder is $0$ then add $d$ and $n/d$ to the factor list. Assuming division and appending to a list are $O(1)$ operations for a CPU, this seems to be $O(\sqrt n)$.

The second is to use trial division with prime factors:

Sieve all primes up to $\sqrt n$. The time complexity of the Sieve of Eratosthenes is $O(n \log \log n)$, so this is $O(\sqrt n \log \log \sqrt n)$?
From that list of primes, repeatedly try to divide by $p$ and move on to the next prime if the current prime will not divide evenly anymore. If it does divide, add $p$ and $n/p$ to the factor list. The density of primes is $n / \ln n$, and since primes go up to $\sqrt n$ the supposed time complexity is $O(\sqrt n / \ln \sqrt n)$. However, this does not take into account dividing by primes more than once.

I would like to know if my analysis is correct. It seems counter-intuitive that trial division only takes $O(\sqrt n)$ time, but $n$ is integer size, not input length. I don't think the time complexity of the second method is correct, but I am sure it must be faster than the first (trying primes instead of all numbers within a range).

The exact running time depends on your computation model. When analyzing arithmetic with large numbers, we usually count either bit operations, or arithmetic operations on words of size $O(\log n)$ (where $n$ is the input size, which in your case is the logarithm of the number you want to factor). This means that in a constant amount of time the first model only allows you to perform an operation involving a constant number of bits; and the second model allows you to perform a constant number of arithmetic operations (addition, subtraction, multiplication, division) on registers of length $C\log n$, where $C$ is some constant which you can use but must depend only on the algorithm.

In both models, the division operation itself won't take $O(1)$; indeed, the CPU cannot divide a large number $N$ by a prime $p$ in $O(1)$. So the running time is really $O(\sqrt{N}(\log N)^{O(1)})$ (where $N$ is the number you're trying to factor). We usually don't care about these logarithmic factors, so we use the notation $\tilde{O}(\sqrt{N})$, and we explain that it hides logarithmic factors.


Sorting algorithm that moves element to a 2-dimensional array I had an idea for a sorting algorithm wich is very fast, but can (potentially) use a lot of memory. I'm not a Computer Science student/graduate, only a self-taught programmer so I don't know how to evaluate it's viability. Also, I would like to know if it has already been documented and under what name.

Algorithm:

Get an unsorted array
Iterate through it, and find the highest and lowest value stored in it
Determine "range" (highest - lowest)
Make a 2 dimensional array presorted,
in which the first dimension's size is "range" + 1
For each element in array "unsorted"

Add the current element into presorted[current_element_value - lowest]

Make array "sorted", and add each element of presorted's second dimension, ignoring the empty first dimensions.
return the sorted array

An example using said algorithm would be the following:

unsorted[] = {5, 8, 2, 4, 6, 8, 2, 0, 4, 5, 6, 3, 3, 2, 1}

After iterating through it once, we get:
lowest: 0
highest: 8

range = highest - lowest = 8

Make 2 dimensional array presorted,
 consisting of range+1 arrays:

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

Next we add the elements, first element of unsorted is 5.
 5 - lowest (0) is 5

presorted[0] = {}
presorted[1] = {}
presorted[2] = {}
presorted[3] = {}
presorted[4] = {}
presorted[5] = {5}
presorted[6] = {}
presorted[7] = {}
presorted[8] = {}

After doing this which each element:

presorted[0] = {0}
presorted[1] = {1}
presorted[2] = {2, 2, 2}
presorted[3] = {3, 3}
presorted[4] = {4, 4}
presorted[5] = {5, 5}
presorted[6] = {6, 6}
presorted[7] = {}
presorted[8] = {8, 8}

Now, we simply create an empty array called "sorted",
 to which we add all the elements
 of non-empty arrays in presorted:

sorted = {0, 1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 8, 8}

This is the C++ source code for it

std::vector<int> Sort(std::vector<int> &unsorted)
{
   int min = unsorted[0];
   int max = unsorted[0];

   int range;

   std::vector<int> sorted;

   for (int i = 0; i < unsorted.size(); i++)
   {
      if (unsorted[i] > max)
         max = unsorted[i];
      if (unsorted[i] < min)
         min = unsorted[i];
   }

   range = max - min;
   std::vector<std::vector<int>> presorted(range+1);

   for (int i = 0; i < unsorted.size(); i++)
       presorted[unsorted[i] - min].push_back(unsorted[i]);

   for (int i = 0; i < presorted.size(); i++)
   {
       if (!presorted[i].empty())
       {
           for (int k = 0; k < presorted[i].size(); k++)
               sorted.push_back(presorted[i][k]);
       }
   }

    return sorted;
}

Is this algorithm viable?

I think it could be used in certain scenarios (when range is not too big) and it has the advantage that you can determine if it's appropriate to use it with simply iterating once through the unsorted list.

I'll do some tests and report back.

What you have come up with is a sligthly less memory efficient version of counting sort.

This algorithm works in $\mathcal{O}(n + range)$ time where $n$ is the number of elements in the vector $unsorted$ and $max$ and $min$ are as defined in your program.

Your implementation uses $\mathcal{O}(n + range)$ memory. You can make it more memory efficient by just keeping track of how many times the same number in the vector 'unsorted' occurs rather than maintaining a vector with repeated instances of the same element i.e.

vector<int> presorted(range+1);
for(int i = 0; i < unsorted.size(); i++)
     presorted[unsorted[i] - min]++

It will now use only $\mathcal{O}(range)$ memory.

Yes you are correct, this method might potentially use up a lot of memory if the difference between the smallest and largest elements of the vector is too great.

For those who are not fluent in C++:

OP is finding the smallest and largest elements of the unsorted array $max$ and $min$ respectively.
He is initializing an array of size $max - min$ and creating an empty linked list in each position of the array (in this code it is the vector of vector of integers $presorted$).
Then each element of $unsorted$ is added as a new node in the linked list at $presorted[unsorted[i] - min]$. In a random access computational model this operation will take $\mathcal{O}(1)$ time and hence each element of $unsorted$ is added to its appropriate bucket in constant time.
Then he is just iterating in the array of linked lists and compressing it to the final array $sorted$ which is the final output.


Vapnik-Chervonenkis Dimension: why cannot four points on a line be shattered by rectangles? So I'm reading "Introduction to Machine Learning" 2nd edition, by Bishop, et. all.  On page 27 they discuss the Vapnik-Chervonenkis Dimension which is,

  "The maximum number of points that can be shattered by H [the hypothesis class] is called the Vapnik-Chervonenkis (VC) Dimension of H, is denoted VC(H) and measures the capacity of H."

Whereas "shatters" indicates a hypothesis $h \in H$ for a set of N data points such that it separates the positive examples from the negative.  In such an example it is said that "H shatters N points".

So far I think I understand this.  However, the authors lose me with the following:

  "For example, four points on a line cannot be shattered by rectangles."

There must be some concept here I'm not fully understanding, because I cannot understand why this is the case.  Can anyone explain this to me?

The definition of "a set $P$ can be shattered by rectangles" is that for every subset of $P$, there is a rectangle that contains precisely that subset and excludes the rest of $P$. Equivalently, every labeling of the points as positive and negative is consistent with at least one hypothesis in $H$.

Now consider four points $p,q,r,s$ along a line in the plane.  Since there is no rectangle that contains $p$ and $r$ but excludes $q$ and $s$, these four points cannot be shattered by rectangles.


Is powerset construction deterministic? Powerset construction is used to convert a non-deterministic finite automaton (NFA) into a deterministic finite automaton (DFA). Is the method/algorithm used to do this deterministic itself and if so, why?

The method itself is (or at least can be made), though the question is somewhat ill posed. What do you mean by deterministic?

The algorithm cannot be run on an NFA or DFA, so it's not deterministic/non-deterministic in that sense.

In most cases, the algorithm will run on a Turing Machine, or some similar model (RAM machine, programming language, lambda calculus, etc.).

It's known that any non-deterministic Turing Machine can be simulated by a deterministic one, using backtracking. So in this sense, the algorithm certainly can be made deterministic.

Is it possible to define the powerset construction in such as way that it's non-deterministic? Yes. There's some element of choice in which states you process first, which NFA states you choose to expand, whether you look breadth-first or depth-first, etc.

But it's trivial to remove these choices, either by resolving them arbitrarily, or by making the choice with some heuristic.


Reduction from Vertex Cover The city council would like to place trash bins around the city and has a list of suitable spots (street crossroads, supermarkets etc.) but the number of these spots is greater than the number of available bins. The council's goal is to place the limited number of bins so that the distance from each house to a bin is at most 100 m. Prove that the problem k containers are sufficient is NP-hard using reduction from a known NP-hard problem.

I came up with vertex cover (could we alternatively use dominating set?). We then need to transform an instance of vertex cover $(V, E, k)$ to an instance of this problem. It's not clear to me how. This is how I thought I would represent the k containers are sufficient problem by a graph:

My first step would be to create a graph where the set of nodes contains both the spots for containers and all the houses. I would then connect each spot node with all the house nodes that it is close enough to (100 m). This seems quite close to vertex cover except that there are 2 types of nodes:

The house nodes cannot be used as a part of the vertex cover set since bins cannot be placed in front of houses but they need to be covered by the vertex cover set.
The bin spots can be used as a part of the vertex cover set but do need to be covered at all by it.

How could I deal with this in the reduction? I thought about using some vertex to edge transformation to represent these relationships but came up short.

This is known as the $k$-center problem or the planar minmax Euclidean facility location problem.  It is a special case of the minimax facility location problem for the Euclidean metric.

The $k$-center problem is known to be NP-hard.  Wikipedia has references to the literature, where you should be able to find an explicit reduction.

The special case where $k=1$ can be solved in polynomial time.


How to convert PDA to CFG I learned how to convert context-free grammar to pushdown automata but how can I do the opposite? to convert PDA to CFG?

For example: to write CFG for the automata

My attempt:

$S=A_{03}$ because $q_{\color{blue}0}$ is the initial state and $q_{\color{blue}3}$ is the final state.

There are $4$ states so we will have $4^2$ variables:

$$A_{00},A_{01},A_{02},A_{03},\\
A_{10},A_{11},A_{12},A_{13},\\
A_{20},A_{21},A_{22},A_{23},\\
A_{30},A_{31},A_{32},A_{33}$$

for each state $q_{i}$ of the automata $A_{ii}\to\varepsilon$

$$A_{00}\to \varepsilon\\
A_{11}\to \varepsilon\\
A_{22}\to \varepsilon\\
A_{33}\to \varepsilon\\$$

For each triplet of states $q_i,q_j,q_k$, we add the rule $A_{ij}\to A_{ik}A_{jk}$, this gives us $4^3=64$ rules:

$$A_{00}\to A_{00}A_{00}|A_{01}A_{10}|A_{02}A_{20}|A_{03}A_{30}\\
A_{01}\to A_{00}A_{01}|A_{01}A_{11}|A_{02}A_{21}|A_{03}A_{31}\\
A_{02}\to A_{00}A_{02}|A_{01}A_{12}|A_{02}A_{22}|A_{03}A_{32}\\
\vdots\\
A_{33}\to A_{30}A_{03}|A_{31}A_{13}|A_{32}A_{23}|A_{33}A_{33}\\$$

I am stuck here.

There is a standard construction to do this, discussed in all formal languages/automata courses. It results in gigantic grammars, often with lots of useless productions and nonterminals.

Added, as requested by Nehorai:

Take a PDA $M = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, \varnothing)$ that accepts $L = \mathcal{N}(M)$ by empty stack (if you have a PDA accepting by final state, first convert to empty stack). We define a CFG that accepts $L$.
The nonterminals are symbols of the form $[p, A, q]$ with $p, q \in Q$, $A \in \Gamma$, and a start symbol $S$. The idea is that if $[p, A, q] \Rightarrow^* \sigma$, then if $M$ starts in state $p$ with $A$ on its stack, after consuming $\sigma$ it might be in state $q$ and the stack is shorter by one symbol for the first time. Consider an $A$ on the (eventually empty) stack as commitment to get rid of it.

If there is a move $(p, A_1 A_2 \dots A_n) \in \delta(q, x, A)$ with $x = \epsilon$ or $x \in \Sigma$, this adds productions:

$\begin{align}
  [q, A, q_n]
    \rightarrow x [p A_1 q_1] [q_1 A_2 q_2] \dots [q_{n - 1} A_n q_n]
\end{align}$

I.e., we consume $x$ from the input (generate it in the grammar), going to state $p$, from which we now are committed to get rid of $A_1 \dots A_N$. We don't know what states $q_1, \dotsc, q_n$ are involved, we just know that after consuming e.g. $A_i$ we will be in some state $q_i$, from which we have to consume $A_{i + 1}$. So we will have to consider all possible collections of states for them.

In the special case $(p, \epsilon) \in \delta(q, x, A)$, the above simplifies to:

$\begin{align}
[q, A, p] \rightarrow x
\end{align}$

If $x = \epsilon$, the above formally doesn't give a context free grammar, but with the standard construction $\epsilon$ productions can be eliminated.

To start the ball rolling, the stack initially contains just $Z_0$, we are in state $q_0$, and end up in any state:

$\begin{align}
S \rightarrow [q_0, Z_0, q]
\end{align}$

for any state $q \in Q$.

This should convince you the above construction is correct. It is far from a proof...


Understanding Regular Grammers I know a regular language is the one which can be expressed as a regular expression or we can create a DFA corresponding to it. Unless a language has a pattern in which one part has to match with other like in $$a^nb^n|n\geq 0 (CFG)$$ It'll be regular. Like AP Series of symbols can be easily expressed as Regular expression but GP Series can not.

But I failed to understand why the following languages are regular

  $L_1=\{wxw^R \mid w,x \in (a,b)^+\}$

  $L_2=\{wxwy \mid w,x,y \in (a,b)^+\}$

  $L_3=\{xwyw \mid w,x,y \in (a,b)^+\}$

All these languages are regular. This comes from the fact $w$ could simply be a single letter, and thus the languages admit the following regular expressions (assuming here $\Sigma=\{a,b\}$, but this would work for any finite alphabet):

$$L_1=a(a+b)^+a+b(a+b)^+b$$
$$L_2=a(a+b)^+a(a+b)^++b(a+b)^+b(a+b)^+$$
$$L_2=(a+b)^+a(a+b)^+a+(a+b)^+b(a+b)^+b$$

A more detailed explanation:

In the definition we had: $w\in\{a,b\}^+$.

This mean that $w$ could be a single letter, $a$, or $b$, and thus we can attribute the rest of the word to $x$ (or $y$).

For example, if:
$$u=abbababa\in L_1$$, because it can be decomposed as $w=a, x=bbabab$ and $$u=wxw^R$$. Similarly, each word which starts and ends with a $a$ is in $L_1$ (pick $w=a$), and each word that starts and ends with a $b$ is also in $L_1$ (pick $w=b$). This is why $$L_1=\{axa|x\in\{a,b\}^+\}\cup\{bxb|x\in\{a,b\}^+\}$$, and thus regular. Same tricks apply to the other languages and all three are indeed regular (by the regex I gave).


Can all permutations of a set or string be generated in O(n log n) time? I was looking over this question requesting an algorithm to generate all permutations of a given string. A comment in the answer caught my eye:

It might seem that it can take O(n) time per permutation, but if you think about it more carefully, you can prove that it takes only O(n log n) time for all permutations in total, so only O(1) -- constant time -- per permutation.

This seemed strange to me because the best method I was aware of to generate all permutations of a string is in O(2^n) time. Looking through the other results, I came across a response to a similar question which states: While it technically produces the desired output, you're solving something that could be O(n lg n) in O(n^n)

I am aware of an algorithm to unrank permutations in O(n log n) time, but these responses seem to imply that all permutations in total can be generated in time O(n log n). Am I misunderstanding these responses?

You have misinterpreted the SO question itself (or we have misinterpreted yours, which seems more likely). That SO quesiton is talking about generating a 'next' permutation from a previous given one, so that all permutations can be generated by calling 'next' multiple times.

The answer to that is talking about the (amortized) time complexity of the C++ implementation std::next_permutation which I believe uses Narayana Pandita's algorithm, and generates them in lexicographic order.

(Also, as an aside: permutations are different from combinations. There are $n!$ permutations, but $2^n$ combinations (subsets). You seem to be under the impression that permutation is same as a combination (based on your claim of $O(2^n)$)).

To get back to the original question, another way to look at the question: would using next_permutation to generate all the $n!$ permutations in lexicographic order be $\Theta(n!)$ or $\Theta(n\times n!)$?

While there are some wrong statements in the answer you linked, it does state the right answer: It is $\Theta(n!)$, i.e. the amortized time complexity of next_permutation is indeed $O(1)$.

This can be proven as follows:

If $T(n)$ is the time taken to generate all the $n!$ permutations using next_permutation then we have that

$$T(n) = n T(n-1) + O(n^2)$$

(You fix the first number $n$ times and generate the permutations for the rest, and pay $O(n)$ cost when the first number is switched.)

Let $G(n) = \dfrac{T(n)}{n!}$. Note that we are looking the the asymptotics of $G(n)$. We get

$$G(n) \le G(n-1) + \frac{cn^2}{n!}$$

This is a simple telescoping sum, and since $\sum_{n=1}^{\infty} \frac{n^2}{n!}$ is convergent, we get that

$$G(n) = O(1)$$

Note that you could have changed the recursion to

$$T(n) = nT(n-1) + O(n^k)$$

and still have gotten $O(1)$ amortized per permutation.


Computational Complexity of a special case of Integer Programming Integer Linear Programming (ILP) is NP-complete. However, there are special instances that can be solved in polynomial time. I am curious about the following integer program (IP) with equations and inequalities in $y_i, c_i, x \in \mathbb Z$ of the following form:

$$\begin{align*}
A_i + B_i y_i+ c_i &= x \\
c_i^2 &> 0\\
c_i^2 &< B_i^2\\
y_i &\geq 0
\end{align*}$$

where $A_i, B_i \in \mathbb N^+$ are given. I wasn't able to find much on this special case. Anyone please?

It is NP-hard, by reduction from 3SAT.

Your problem is equivalent to the following: given a system of inequalities of the form $x \not\equiv A_i \pmod{B_i}$, where the $A_i,B_i$ are given, test whether any solution exists.  (Why?  If $0 < c_i^2 < B_i^2$ then $c_i \not\equiv 0 \pmod{B_i}$, and vice versa.)

Now 3SAT can be reduced to this problem (satisfiability of a system of inequalities), so it follows that this problem is NP-hard.  Here's how the reduction works.

Let $\varphi$ be a 3SAT instance, with variables $v_1,\dots, v_n$.  Let $p_1,\dots,p_n$ be the first $n$ primes.  Add inequalities of the form $x \not\equiv 2 \pmod{p_i}$, $x \not\equiv 3 \pmod{p_i}$, ..., $x \not\equiv p_i-1 \pmod{p_i}$ for each $i$, forcing $x$ to be either 0 or 1 modulo each prime.  Now, suppose we have a clause $v_i \lor v_j \lor v_k$.  This translates to an inequality $x \not\equiv 0 \pmod{p_i p_j p_k}$.  The clause $v_i \lor \neg v_j \lor v_k$ translates to $x \not\equiv \alpha \pmod{p_i p_j p_k}$ where $\alpha$ is the unique value such that $\alpha \equiv 0 \pmod{p_i}$, $\alpha \equiv 1 \pmod{p_i}$, and $\alpha \equiv 0 \pmod{p_i}$ (you can find $\alpha$ using the Chinese remainder theorem).  And so on -- in this way, each clause can be translated into an inequality.

Finally, there exists a value $x$ that satisfies all of these inequalities if and only if there exists an assignment that satisfies $\varphi$.  (Why?  $x\equiv 1 \pmod{p_i}$ corresponds to setting $v_i$ to true, and $x\equiv 0 \pmod{p_i}$ corresponds to setting $v_i$ to false.  You can then verify equivalence between clauses and inequalities.)  Since the resulting system has size polynomial in $n$, this gives a polynomial-time reduction from 3SAT to your problem.


What is the optimal algorithm for finding all sets of overlapping ranges? I have a set of (integer) ranges and want to compute the (possibly non-disjoint) set of all subsets of overlapping ranges. The data structure used for the output is not of particular importance to me; if a linked list can be used to reduce the run time, for example, then that's alright with me.

Formal problem

Consider a set of integer ranges $R$. Find the largest set $O = \{ R_i \subset R \}$ where each (non-empty, unique) $R_i$ satisfies $\forall r, r' \in R : r \ \text{overlaps}\ r' \iff r, r' \in R_i$.

What is the algorithm with the lowest known time complexity for solving this problem?

Sort the ranges by their start points. Then your overlapping ranges can be found in $O(k + n)$ where $k$ is the number of overlapping pairs and $n$ is the input size simply by a double loop. In C:

int i, j;
for (i = 0; i < n; ++i) {
    int start = start_points[i];
    for (j = i + 1; j < n && start_points[j] < end_points[i]; ++j) {
        output(i, j);
    }
}


Decoding bit streams using Hamming Code I want to decode the following bit stream using Hamming code:
01110110

Once using even parity and once odd parity. I will show my work. For even parity:

$p_{1} \; p_{2} \; 0 \; p_{3} \; 1 \; 1 \; 1 \; p_{4} \; 0 \; 1 \; \; 1 \; 0$

Now, we check:

$p_{1}: p_{1}  \; 0 \; 1 \; 1 \; 0 \; 1 $, since there is an odd number of 1's, $p_{1}=1$

$p_{2}: p_{2}  \; 0 \; 1 \; 1 \; 1 \; 1 $, since there is an even number of 1's, $p_{2}=0$

$p_{4}: p_{3}  \; 1 \; 1 \; 1 \;0 $, since there is an odd number of 1's, $p_{3}=1$

$p_{8}: p_{4}  \; 0 \; 1 \; 1 \;0 $, since there is an even number of 1's, $p_{4}=0$

so the following hamming code is
$$1 \; 0 \; 0 \; 1\; 1 \; 1 \; 1 \; 0 \; 0 \; 1 \; \; 1 \; 0$$

As for odd, the parities will just be the opposite and the code will be

$$0\; 1 \; 0 \; 0 \; 1 \; 1 \; 1 \; 1 \; 0 \; 1 \; \; 1 \; 0$$

Can someone tell me if my work is correct? Because I am a bit confused and would appreciate the help.

There are many equivalent Hamming codes depending on the ordering of parity and data bits.
Assuming that:

You are using the specific bit ordering described here: https://en.wikipedia.org/wiki/Hamming_code#General_algorithm
By "even parity" you mean that the parity bits are computed as the sum (modulo 2) of the corresponding groups of bits
By "odd parity" you mean that the parity bits are computed as 1 minus the sum (modulo 2) of the corresponding groups of bits,

then yes, your simulation of the algorithm is correct.


If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$ Language $L$ is trivial if $L=\varnothing$ or $L=\Sigma^*$. I'm trying to prove the following theorem:

If $L_1\in R$ and $L_2$ is non-trivial language then $L_1\leq L_2$.

If $L_2$ is non-trivial the  $L_2\neq\varnothing$ and $L_2\neq\Sigma^*$. If I want to prove that $L_1\leq L_2$, then I need to show that there exists $f:\Sigma^*\to\Sigma^*$ which is total, can be calculated by a Turing machine and follows: $\forall x\in\Sigma^*$, $x\in L_1$ iff $f(x)\in L_2$. I also know that $L_1\in R$ then there is a turing machine $M_1$ that decides language $L_1$. But how do I continue from here? How $f$ should look like?

We know there are two $x_1,x_2\in \Sigma^*$ such that $x_1\in L_2$ and $x_2\notin L_2$, since $L_2$ is not trivial. Now, we will build the following reduction:
$f(x)=\cases{x_1 & $x\in L(M_1)=L_1$ \\ x_2 & otherwise}$
Notice that $f$ is computable: calculate $M_1(x)$, and output either $x_1$ or $x_2$ according to the answer you got.


Proccess scheduling arrival time If I have a set of processes, let's say 9 and I know the burst time and the waiting time for SJF algorithm and also know that processes arrive in groups of 3 processes at M1 moment, M2 moment,  M3 moment (M1, M2 and M3 are given), how can I decide at what moment each process will arrive?

What are their execution time and  possible start time and finish times? For each process time, its execution time is $\text{TAT}-\text{WT}$. Its start time should be WT plus one of 0, 12 and 24. Its finish time should be TAT plus one of 0, 12, 24.

$$
\begin{array}{|c|c|c|c|c|}
\hline
\text{Process} & \text{WT} & \text{TAT}&\text{Execution Time} & \text{Start Time} & \text{Finish Time} \\\hline
P1 & 6 & 15 &9 & 6, 18, 30 & 15, 27, 39  \\\hline
P2 & 3 & 6 &3 & 3, 15, 27 & 6, 18, 30 \\\hline
P3 & 63 & 84 & 21 & 63, 75, 87&84, 96, 108  \\\hline
P4 & 0 & 6 & 6 & 0& 6\\\hline
P5 & 24 & 36 & 12 & 24, 36, 48& 36, 48, 60\\\hline
P6 & 7 & 15 & 8 & 7, 19, 31 & 15, 27, 39\\\hline
P7 & 24 & 39 & 13 & 24, 36, 48 & 39, 51, 63\\\hline
P8 & 6 & 12 & 6 & 6, 18, 30 & 12, 24, 36\\\hline
P9 & 3 & 7 & 4 & 3, 15, 27 &7, 19, 31\\\hline
\end{array}
$$

What can we say about start times and finish times?

The start time of any process except the first process must be the finish time of another process.
The finish time of any process except the last process must be the start time of another process.

What does it mean by SJF? It means among all jobs that have been queued/submitted, the shortest job will be executed first.

So our task is to select 10 numbers $0, 6, \cdots$ from the column "Start time" and "Finish Time" so that

each number must appear in column "Start Time" and column "Finish Time", except the first number 0, which only appears in column "Start Time" and the last number, which only appears in column "Finish time".
The sequence starts with 0, 6 since, as you have observed, the first process started at 0 and ended with at 6.
For the initial numbers that are not greater than 12, their successive differences should become bigger and bigger. For the next segment of numbers that are not greater than 24, their successive differences should become bigger and bigger. For the last four numbers, their successive differences should become bigger and bigger.

There should be enough hint to set you moving again.

Just in case you are still stuck, move your mouse over the following to reveal the spoiler.

   Check the column "Finish Time". Which process must finish last? Then which process' finish time could be the last process' start time? Then which process' finish time could be that process' start time? And so on.

 It turns out the condition SJF is not needed at all. This problem can be solved as long as the processes are executed one after another.

 On the other hand, SJF can be helpful. The three processes with longest execution time, P3, P5 and P7 must be the last three jobs since all of them started later than 24. Since SJF, $P5\prec P7\prec P3$.


What is a visual bag of words and how is it implemented? I'm currently working on implementing a bag of visual words in Python. I get the general gist of how it works but I can't seem to find any sources that explain it in more detail to a level where I can implement it. I'm guessing scikit learn and scikit image would come in but I can't seem to point myself in the right direction. Any help?

This is the original paper:

Gabriella Csurka, Christopher R. Dance, Lixin Fan, Jutta Willamowski, and  Cédric Bray. Visual Categorization with Bag of Keypoints. Workshop on Statistical Learning in Computer Vision, ECCV, 2004.


O(1) distinct elements in an array implies? Could someone explain the following question -

Given the following statement viz. Consider an input array a[1..n] of arbitrary numbers. It is given that
the array has only O(1) distinct elements. What does the statement imply ?

Thanks.

Essentially, it means no matter what the size of the array is (namely, no matter what $n$ is), it will have no more than a fixed constant number of distinct elements. This assumes that you know what the term $O(1)$ means. If not, ask for clarification.


Solving a recurrence relation with T(n) = 2 * T(n/3) + 5n I have no idea how to solve this one - I end up with $\sum_{i=0}^k (2^k * 5 * 3^i)$ but I have no clue how to get any further than that (e.g. resolve the sum even further, if it's even correct to begin with).

This is the task - masters theorem is not allowed:

T(n) = 2 * T(n/3) + 5n

T(1) = 5

and we know, that n = 3^k

Thanks for all of your advice & help!


Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes.

I tried to look it up at a few places (including Sipser) but I could not make out a lot of sense from the proofs. I would appreciate it if someone can give me a proof (or clear intuition) on this.

Let $R(s,t)$ be the least integer $k$ such that every graph on $k$ or more vertices contains either a $s$-clique or independent set of size $t.$

It turns out that this number is well defined (called Ramsey number) and the statement in your question merely amount to saying that $$R(t,t) \leq 2^{2t}.$$

A well known upper bound for Ramsey number states $$R(s,t) \leq R(s,t-1)+R(s-1,t) \leq {s+t-2 \choose t-1} \; \; \; (1)$$ if $s = t$ then the above reduces to the central binomial coefficient ${2t-2 \choose t-1}$ which is always smaller than $2^{2t}$

To prove $(1)$ one can use induction on $s+t$.  Leaving the induction base $R(1,t), R(s,1)$ as an exercise for you let us suppose the inequality holds for all $s+t < k$ and let $G$ be a graph with $R(s,t-1)+R(s-1,t)$ vertices.

Let $v$ be an arbitrary vertex of $G$ and partition the remaining vertices of the graph into two groups $A,N$ - those adjacent with $v$ and those that are not adjacent with $v.$ Now since $$|A|+|N|+1 = R(s,t-1)+R(s-1,t)$$ we have either $$|N| \geq R(s,t-1) \quad \mbox{ or} \quad |A| \geq R(s-1,t).$$ Now if the first inequality is satisfied then the graph induced by $N$ either contains a $s$-clique or the graph induced by $N \cup \{v\}$ contains an independent set of size $t.$ In particular this implies that in this case $G$ either contains a $s$-clique or independent set of size $t.$ The second case is verified analogously and establishes the first part of the stated bound. For the last part observe that $${s+t-3 \choose  s-1} + {s+t-3 \choose s-2} = {s+t-2 \choose s-1}.$$


reducing the halting problem to the blank tape problem I have checked many discussions for understanding this problem.

I understand the reasoning , unfortunately there are some drawback in my understanding.

The Blank-tape halting Problem

Input: Turing Machine M

Question : Does M halt when started with a blank tape?

So this is the reduction :

The construction of Mw is as follows :

When started on blank tape, writes w
Then continues execution like M

What i don't undesstand is the step 2 , in my opinion if we execute M on w maybe M will loop !!!

My second question : what the blank-tape do when executed?even if the blanktape machine halt on blank tape , how can we be sure that M halt on w .i miss something here.

Thank you in advance.

The reduction does not actually execute $M$, what its actually doing is the following mapping:

$\big(\langle M\rangle,w\big)\mapsto \langle M_w\rangle$

Where $M_w$ is the machine that when executed with blank tape, simulates the machine $M$ on input $w$. Preforming the reduction does not require that you execute $M$, you simply need to write down the code of $M_w$. Obviously $M$ halts on $w$ iff $M_w$ halts when executed with blank tape (we constructed $M_w$ specifically for this purpose), and the correctness of the reduction follows.


How to perform bottom-up construction of heaps? What are the steps to perform bottom-up heap construction on a short sequence, like 1, 6, 7, 2, 4?

At this link there are instructions on how to do for a list of size 15, but I can't [necessarily] apply the same process to a list of 5 items (my trouble is that 5 is not enough to provide a complete tree).

Five nodes is plenty to make a tree. See for example here. His first example has 6 nodes, not 5, but it should get you started.

A heap is a binary tree with all levels filled except, perhaps, the last. The last level is filled in left-to-right until you run out of elements.

So yours would start out like this:

The heap invariant is that each parent is smaller than both its children. In the heap construction algorithm you work bottom up, restoring the heap invariant. One way to do this is a recursive post-order tree traversal:

Heapify (x):
    if (x->is_leaf) return x
    l = Heapify (x->left_child)
    if (exists(x->right_child)):
        r = Heapify (x->right_child)
        if ((r->value < x->value) && (r->value < l->value)):
            swap(r->value, x->value)                    # r->value was smallest
    if (l->value < x->value):
        swap(l->value, x->value)                        # l->value was smallest
    return x

In actual code for heaps the heap is often represented as an array with the elements stored top-to-bottom and left-to-right in each level. The first element is the root, the second and third elements are the children of the root, and so on. In this case you can do the initial heap creation by working backwards through the array to get a post-order tree traversal for cheap (i.e., as an iterative algorithm that doesn't need to recurse).


Origin of "Cookie" in Computing? "Cookies" are a user-facing computing construct. They are codified in many technical specifications, including the earliest reference in an HTTP spec, RFC 2109, published February 1997.
Many claim the use in HTTP followed from UNIX "magic cookies." Eric Raymond provided a definition of what a "magic cookie" is:

Something passed between routines or programs that enables the receiver to perform some operation; a capability ticket or opaque identifier [...]

OK.
But why did the UNIX community start using the phrase "cookie" to begin with? Is it because you put cookies into a jar, and take them out? When did this whole thing begin? Does anyone have a citation of the first usage?

According to the Wikipedia article on magic cookie, it was used already in 1979 in the manpage of fseek. The talk page of the Wikipedia article on magic cookie discusses questions regarding the origin and meaning of the word. The following quote of Douglas W. Jones from the talk page nicely summarizes it:

Once upon a time, I asked Dennis Ritchie about the origin of the term magic cookie as used in the man page for ftell and fseek in the C library. He said that, so far as he knew, the usage in that man page was a new coinage. That man page is not present in V5 UNIX but it is present in the manuals for V7 UNIX and 4.2BSD. I have quoted the relevant sentence from that manual on the Wikipedia page; the wording makes it clear that the meaning is the same as the contemporary meaning for magic cookie (in the broader sense than HTML cookie). Any speculation about derivation from cookie monsters or LSD cookies seems, at this point, irrelevant compared to tracking down the first use of the term in its modern sense. Douglas W. Jones 21:15, 24 February 2017 (UTC)


Does the specific size of matrices affect the performance of matrix operations? I was reading DeepMind's paper on I2A's and realized that the sizes of the hidden layers in their model were all like 32, 64, 256, and so on: all powers of 2. I have found the same thing in other papers.

Is there any performance reason for it? Maybe related to data structure alignment?

More concretely, I would like to know if I should use this "special" sizes when training my own models.

While you can only be 100% certain when you ask the authors, most authors use this simply because you have to choose one value. The specific value doesn't matter too much, only the order of magnitude. Taking a power of 2 seems to be a natural choice.

You can also take a setup which uses a power of two and reduce the number by one. The computation time should be roughly equal, probably be a bit lower. If it is noticeably higher, there might be a performance benefit of using the choice of the author.

See also

Datascience.SE: Why the number of neurons or convolutions chosen equal powers of two?
Quora: Should I use powers of 2 when choosing the size of a batch size when training my Neural Network?


How to simplify the sum over 1/i? With the recurrence relation:
$$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$

The "sum for all levels" in the recurrence tree is:
     $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} =  \sum_{i=1}^{\log n} \frac{n}{i} = n \sum_{i=1}^{\log n} \frac{1}{i}$$

Inside the analysis of the recurrence, $\sum 1/i$ appears and then bounded by $\Theta(\log\log n)$. Why is this?

$\sum_{i=1}^k\frac{1}{i}$ is the $k$th harmonic number, which is $\Theta(\log k)$.


2 threads accepted at the same time Assuming we have an automaton that simultaneously accepts a string on two paths. Would this mean that the construction of the NFA might be faulty?  In other words; at the end of any string over any alphabet, does the NFA have to end up accepting one single path only? Or could it accept several at the same time?

A NFA is defined so that if there is any accepting path for the given input string, it will accept. It's perfectly allowable for an NFA to have two paths to acceptance. If no path accepts, then the NFA doesn't accept.


How to find examples of best cases for sorting algorithms? I am asked to give a table of 8 elements that are to be sorted by the following algorithms and to produce their best cases.
1) Selection sort
2) Bubble sort
3) Insertion sort
4) Fusion sort

If I give an already sorted table ex: {1,2,3,4,5,6,7,8} shouldn't it already be the best case for all of them? If I can be considered a best case for each?

Bubble sort can "stop early" should the array already be sorted. Other algorithms have their own advantages or applications, but none of the algorithms mentioned in your question - other than bubble sort - can "stop early".

Therefore for any input Insertion & Selection runtime will be $\Omega (n^2) $, and Mergesort $\Omega(nlog(n))$, so the order of elements doesn't matter at all.

$\bullet $ If you perform bubble sort on an already sorted array, the algorithm can stop when not performing any swaps, and run at $O(n)$

$\bullet $ Merge sort (to which you refer as 'fusion sort' from some reason) is the only algorithm that requires $O(nlog(n))$ rather than $O(n^2)$

$\bullet $ Insertion sort is useful when receiving the array online (one element at a time) and maintaining it sorted. Its noteworthy that since you maintain a sorted array, new elements can be inserted via binary search, which make the insertion sort perform $O(nlog(n))$ comparisons, but still cost $O(n^2)$ due to moving elements.

$\bullet $ Selection sort is very easy to implement and intuitive to explain


Count number of pairs of elements whose product is a perfect square Given two arrays whose elements lie between $[1,10^5]$ and the size of arrays is $[1,10^5]$, how can we find the total number of pairs of elements from these arrays such that their product is a perfect square? The arrays may have same elements.

For example:

  Array 1: {1, 2, 4, 5}

  Array 2: {4, 8, 16, 125}

  Output : 6

The pairs are (1, 4), (1, 16), (2, 8), (4, 4), (4, 16), (5, 125).

If the array size is $10^5$, an $n^2$ algorithm would be inefficient.

There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a_x,b_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum_x a_x b_x$.

There are many optimizations possible for this general scheme, which in practice can speed it up significantly. I'll let you work them out.


Order notation subtractions in Fibonacci Heap Can order notation on its own imply:

$O(D(n)) + O(t(H)) - t(H) = O(D(n))$

My guess is that you cannot since the constant in the O(t(H)) would still exist after the subtraction if the constant is > 0.

Well, this is actually the case, but there are underlying factors. This equation appears in Fibonacci heap analysis in CLRS (518). The justification for this step comes from the underlying potential function. According to the authors, "we can scale up the units of potential to dominate the constant hidden in $O(t(H))$". I want to know how this happens, but don't really know how to ask this complicated question.

As you point out your first equation is not necessarily correct.

Let me rewrite it by explicitly adding the multiplicative constants:
$\alpha D(n) + \beta t(H) - \gamma t(H) = O(D(n))$, where $\gamma =1$.
Here the problem is that $\beta$ might be larger than $\gamma = 1$.

What the authors are saying is that instead of thinking that one unit
in the value of your potential function $\Phi(H)$ contributes one unit of potential, you can imagine that it is actually representing $\gamma$ units of potential.
This amounts to redoing the analysis with a new potential function $\Phi'(H)$ defined as $\Phi'(H) = \gamma \cdot \Phi(H)$. If you do so, then you are able to control the value of $\gamma$ in the above equation, while $\beta$ stays the same.

Picking a value of $\gamma \ge \beta$ ensures that
$\alpha D(n) + \beta t(H) - \gamma t(H) = \alpha D(n) -  \underbrace{(\gamma -\beta)}_{\ge 0} t(H) \le \alpha D(n) = O(D(n))$, as desired.


Linear time algorithms on regular graphs For each constant $k$, the number of $k$-regular graphs is of the order of $n^{\Omega(n)}$. Therefore, we need $O(n\log n)$ bits to represent k-regular graphs unambiguously.

Let $k=3$ for simplicity. There are several algorithms
that run in time $O(n)$ on $3$-regular graphs with at most $n$ vertices.
For instance, determining if a graph is bipartite.

How is that possible, if only to read the input we need to read $O(n\log n)$ bits?

We usually analyze algorithms on the RAM machine model, in which each operation on a machine word has unit cost. A machine word consists of $O(\log n)$ bits, where $n$ is the bit-size of the input, or some other equivalent property. Thus representing a $k$-regular graph takes only $O(n)$ machine words, so there is no contradiction.