Notations around the polynomial hierarchy I am new to "Computational Complexity" and therefore I have enough problems with some exercises like the following one:

  Remember: $\text{PH} := \bigcup_{i} \Sigma_i$

  Show:

  $\bullet \bigcup_{i}(\Sigma_i \cup \Pi_i \cup \Delta_i) = \bigcup_{i}\Sigma_i = \bigcup_{i}\Pi_i = \bigcup_{i}\Delta_i$

  $\bullet \forall k \in \mathbb{N} (\Sigma_k = \Pi_k \Rightarrow \text{PH} = \Sigma_k)$

I have tried to make myself familiar with Polynomial hierarchy, but on the one hand I don't understand the meaning of the symbols $\Delta, \Sigma, \Pi$ and on the other hand I don't know how to solve the actual exercise.

Can somebody give me some help, please?

$\newcommand{\P}{\mathsf{P}}\newcommand{\PH}{\mathsf{PH}}$
$\newcommand{\SUM}[1]{\Sigma_{#1}^{\P}}\newcommand{\PROD}[1]{\Pi_{#1}^{\P}}$
$\newcommand{\DELTA}[1]{\Delta_{#1}^{\P}}$
$\newcommand{\NP}{\mathsf{NP}}\newcommand{\coNP}{\mathsf{coNP}}$
From the comments:

  Why is $\SUM{1} = \NP$?

Recall the definition of $\NP$ using certificates/proofs:

  A language $L$ is in $\NP$ if there exists a poly-time TM $M$ and a polynomial $q$ such that $$x \in L \iff \exists u \in \{0,1\}^{q(|x|)}\ M(x, u) = 1$$

This is also exactly the definition for $\SUM{1}$. In the case of $\NP$ it is a single existential ($\exists$) quantifier. Now, the negation of existential quantifier is the universal quantifier ($\forall$). If we swap out the quantifiers in the certificate definition of $\NP$ we have $$x \in L \iff \forall u \in \{0,1\}^{q(|x|)}\ M(x, u) = 1$$ which is exactly $\coNP$ (and denoted in the hierarchy as $\PROD{1}$)! We see that $\PH$ is just a generalization of this, by allowing more (alternating) quantifiers.

For the first bullet:

  $\bigcup_{i}(\SUM{i} \cup \PROD{i} \cup \DELTA{i}) = \bigcup_{i}\SUM{i} = \bigcup_{i}\PROD{i} = \bigcup_{i}\DELTA{i}$

Sketch: It is straightforward to show that $\SUM{i} \subseteq \PROD{i+1} \subseteq \SUM{i+2}$. The reasoning is that you can simply "ignore" the leading quantifiers in the verifying TM. Likewise, we see $\SUM{i} \subseteq \DELTA{i+1} \subseteq \SUM{i+1}$. Again, this can be explained due to the fact that both $\DELTA{i+1}$ and $\SUM{i+1}$ have oracle access to $\SUM{i}$ with the difference being that $\SUM{i+1}$ is an $\NP$-based machine whereas $\DELTA{i+1}$ is a $\P$-based machine.

With the subset relation in-hand, we see that a union over all integers will cover all cases.

Now for your second bullet:

  $\forall k \in \mathbb{N}\ \  \SUM{k} = \PROD{k} \Rightarrow \PH = \SUM{k}$

Proof: This can be shown by induction on $k$. For our base case let $k = 1$ and observe that if $\SUM{1} = \PROD{1}$ then a collapse occurs. To see this, let $Q_1, \cdots, Q_i$ be the alternating quantifiers for some level $i$ in the hierarchy. Since $\SUM{1} = \PROD{1}$, we can replace each universal quantifier in the sequence with an existential quantifier resulting in $\exists u_1, \cdots, \exists u_i$. But by definition of the quantifiers, we can reduce this to a single $\exists \langle u_1, \cdots, u_i \rangle$ which is exactly $\SUM{1}$.

Now assume this holds for all values less than $k$. Given level $\SUM{k}$ we can decompose its quantifiers into two parts, the initial $\exists u_1$ and the following alternating sequence $\forall u_2, \cdots, Q_{k} u_{k}$, where $Q_{k}$ is either $\exists$ or $\forall$ depending on whether $k$ is odd or even. Observe this sequence is exactly $\PROD{k-1}$ which by our hypothesis is equal to $\SUM{k-1}$. By substituting and combining the initial term we have $$\exists \langle u_1, u_2 \rangle, \cdots, Q_{k} u_{k}$$ which is really only $k-1$ terms! Therefore a collapse occurs.


What does $\omega{(1)}\cdot O(logN)$ mean? What does $\omega{(1)}$ mean as a factor?
In some papers, there exists some asymptotic analysis which comprises a product of multiple Landau notation like $\omega(1)\cdot O(logN)$.
In this example, what is the meaning of the additional factor $\omega(1)?$

It presumably means a product of the form $f(N)\,g(N)$, where $f(N)\in\omega(1)$ and $g(N) \in O(\log n)$.

However, that's a very strange thing to write, since every well-behaved function $h$ can be written in this way. If $h\in\omega(1)$, write it as $h(N)\cdot1$, which is valid, since $1\in O(\log N)$; if $h\in O(1)$, write it was $N\cdot (h(N)/N)$.


left/right derivations of grammars and parse trees I'm having a hard time understanding how left/right derivations work. I have a very simple example that I've attempted but I don't really know how to check if it's correct.
$S-> NP$ $V$ $NP$
$NP ->$ the $N$
$N ->$ cat | mouse
$V ->$ ate
LEFT
$S-> NP$ $V$ $NP$
$S->$ the $N$ $V$ $NP$
$S->$ the $N$ $V$ the $N$
$S->$ the cat $V$ the $N$
$S->$ the cat ate the $N$
$S->$ the cat ate the mouse
RIGHT
$S->NP$ $V$ $NP$
$S->NP$ $V$ the $N$
$S->$ the $N$ $V$ the $N$
$S->$ the $N$ $V$ the mouse
$S->$ the $N$ ate the mouse
$S->$ the cat ate the mouse
My Thoughts
My lecture material says that we operate on the left/rightmost non terminal, I'm not 100% sure how to differentiate terminals and non-terminals but I assumed that if it became an English word it was a terminal hence I skipped it as long as there was a production remaining with another identifier in it.
Parse Tree
I genuinely don't know how to create the parse trees and I appreciate any input in helping me figure it out.
edit: I forgot to mention, I know that the parse tree should be the same for the left and right derivation of the above grammar, just don't know how to build one, all examples I find online are too complex for my understanding, I just started learning about this stuff very recently.

A non-terminal is something with a production rule. You're correct that words aren't non-terminals. They are terminal precisely because there is no production which expands the word.
In a leftmost derivation, every step must expand the leftmost non-terminal. The leftmost non-terminal is the non-terminal which is closest to the left :-). In $\text{the N V NP}$ , the leftmost non-terminal is $\text{N}$. So if you choose a derivation step which expands $\text{NP}$, that's not a leftmost derivation.
In a parse tree, the root is whatever the root of the grammar is ($\text{S}$ in this case) and each node has as its children the symbols on the right-hand side of the production which is used the expand that particular non-terminal. Terminals are leaf nodes; they have no children.


Is pumping lemma for regular languages "closed" against Kleene star? If I have an infinite language $L$ which fulfills the Pumping lemma for regular languages, does $L^*$ also fulfill the same conditions?

In order to show the pumping property of a string like $x_1x_2 \dots x_n$, where each $x_i\in L$ you can distinguish two cases. Either $x_1$ is "short", which means you can pump $x_1$ completely and stay within $L^*$, or $x_1$ is "long" and you can pump "inside" $x_1$.


Algorithm to travel all edges only once I have a directed, unweighted graph that obeys the following rules:

The number of nodes and edges is finite
Each node can eventually be reached from any other node by some path
Each node has an equal number of incoming and outgoing edges

Like this:

I am trying to develop and algorithm that starts in any node and travels each edge of the map once and only once but I'm struggling to come up with anything.

I've thought about finding an algorithm to hit each node and then following it out and back but this can easily be done without traveling every path. (In the graph above you could go a->d->g->e->b->c->f->c->b->e->g->d->a but never hit the paths connecting d to e or the paths connecting e to f)

I've also tried to come up with something like the corn maze solution where you always take the left most available path, but this too has the potential to leave out large chunks of the graph. (you could go a->d->a and think you were done)

I think in order to do this I probably need to be keeping track of which nodes I've already visited and how many remaining untraveled edges it had and always choose to travel to the node with the max remaining untraveled edges. But I feel like this has errors too where I could trap myself into part of the graph  though I haven't found a good example where it does so. Any way to prove the correctness of this or find a counterexample (and in that case maybe thoughts on a new possibility) would be greatly appreciated! I've found a counter example:

Consider the following graph with moves marked in red and remaining count at each node marked in blue, at this point, you are in node b, and can move to either a or c because they are equally weighted, if you move to a, you have effectively cut yourself off from ever traveling the b->c paths.

So now I'm at even more of a loss :/

You are trying to find an Euleran path in a graph.

Observe, that if each node has equal number of incoming and outcoming edges, every time you enter a node using an edge you have not used before, there is an unused outgoing edge. The only vertex that does not have this property is the starting vertex. Therefore, any path that starts in vertex $v$ can either be easily extended or end in $v$, resulting in a cycle.

The only problem we now have to take care about is covering all the edges. After you finish a cycle and can't proceed, take any vertex $t$, which is in your cycle and has some unused edges. Start a new cycle from $t$, obviously using only unused edges. Connect the new cycle with the old one. Iterate until finished.


Skip List estimate number of elements less than (or greater than) a value I am looking for a thread safe data structure where

an element can be searched in $O(\log n)$,
for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,
an element can be inserted in $O(\log n)$, and
an element can be removed in $O(\log n)$.

Can a skip list or some modification of it be used?  Is there an alternative data structures (Parallel Red-Black Tree for example) that can be used?

Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach.  Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.).  Annotate each node with the size of the subtree under that node.  Then, make this data structure persistent.  This can be done in a straightforward way using path copying.

Because the data structure is persistent, it handles concurrency nicely.  In particular, immutable data structures are inherently good for concurrency; you don't have to worry about two threads writing to it concurrently, since it is immutable.  Instead, updates essentially work by creating a new copy of the data structure.  Thus, each thread has its own copy of the tree.  The only shared variable you need is a single global variable that holds a pointer to the current copy of the tree.  To update the tree, a thread reads the pointer in that global variable; makes a new copy of the tree with the update; then does a compare-and-swap to update the value of the global variable (unless it has changed since last reading it, in which case you cancel the operation and retry).  Because each thread works on its own local copy of the tree during updates, you don't have to worry about some other thread concurrently accessing that copy.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.


How do I get the solution for a recursion with n! using Master Theorem? The problem in my book is T(n) = 16T(n/4) + n!

I don't know how to get at the correct solution my book has, which says Θ(n!)

here are pictures of the master theorem and the problem in my book.

Suppose for simplicity that we only consider $n = 4^k$, and that $T(1) = 1$.

Let us guess that $T(n) \leq Cn!$ (where $C>0$), and try to prove it by induction. For the inductive step we need
$$
16C(n/4)! + n! \leq Cn!,
$$
that is,
$$
16C(n/4)! \leq (C-1)n!.
$$
For the base case we need $C \geq 1$.

Let us write the inductive constraint for $n = 4$:
$$
16C \leq 24(C-1) \Longrightarrow C \geq 3.
$$
This prompts us to choose $C = 3$. For $n \geq 4$ we then need
$$
48 (n/4)! \leq 2n! \Longleftrightarrow \frac{n!}{(n/4)!} \geq 24.
$$
It is easy to check that this always holds – for $n = 16$ it's a simple computation, and for $n \geq 64$ we have $n!/(n/4)! \geq n > 24$.

Intuitively, what is happening here is that $(n/4)!$ is much much smaller than $n!$, and so $T(n) \approx n!$, since all other summands (which you see if you unroll the recursion) are so much smaller.


Maximum product of contiguous subsequence over $\mathbb{R}$ For the problem of a subsequence of maximum product with negative, zero and positive integers, I have the following working solution (inspiration from here).

Let us first show how to solve the problem when the array contains no zeroes:

If there is a single entry, return the entry.
If the number of negative entries is even, return the product of all elements.
Otherwise, let the array be $A_1,\ldots,A_n$, let the index of the first negative element be $i$, and let the index of the last negative element be $j$. Return
$$
\max \left( \prod_{k=i+1}^n A_k, \prod_{k=1}^{j-1} A_k \right).
$$
(Since $n > 1$, both sums are non-empty.)

For a general array which is not all zeroes, we partition in into maximal subarrays with no zeroes, apply the preceding procedure to each subarray, and return the maximum over all outputs.

Besides this solution, I also have a dynamic programming solution inspired largely from the problem of maximum sum subsequence that works for positive real numbers but not for negative numbers.

Given an array $A_1,\ldots,A_n > 0$, we compute an array $S_1,\ldots,S_n$ such that $S_i$ is the maximum product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$:
$$
S_1 = A_1, S_{i+1} = \max(A_{i+1}, S_i A_{i+1}).
$$
The answer is then $\max(S_1,\ldots,S_n)$.

I would like to know how to change the first solution to handle general numbers rather than only integers, and to understand how these changes work.

I tried to find a data structure for the problem with floating-point numbers, I thought of using $P_{\min}$ and $P_{\max}$ matrices where $P_{\min\ i, j}/P_{\max\ i,j}$ is the minimum/maximum product that can be computed from a subsequence in the $A_i,\ldots,A_j$ subsequence, but I could not find a recursive relation between the elements of the matrices. I think I found some sort of heuristic method using $P_{\min}$ and $P_{\max}$ as vectors that are updated in a single iteration of $A$, each value of $P_{\min}$ depending on $A$ and $P_{\max}$, and each value of $P_{\max}$ depending on $A$ and $P_{\min}$, but I did not test how adequate it is.

An example of why the first algorithm in my question is not working for floating-point numbers is the input $2, 2, 0.1, 2, 2$.

You can adopt the dynamic programming solution; the other solution looks harder to adapt.

Given an array $A_1,\ldots,A_n$, we let $P_i$ be the maximum positive product of a subsequence of $A_1,\ldots,A_i$ containing $A_i$, and we let $N_i$ be the minimum negative product of such a subsequence. If no such subsequences exist, we let $P_i = 0$ or $N_i = 0$.

Initialization:

If $A_1 = 0$ then $P_1 = N_1 = 0$.
If $A_1 > 0$ then $P_1 = A_1$ and $N_1 = 0$.
If $A_1 < 0$ then $P_1 = 0$ and $N_1 = A_1$.

Iteration:

If $A_i = 0$ then $P_i = N_i = 0$.
If $A_i > 0$ then $P_i = \max(A_i, A_i P_{i-1})$ and $N_i = A_i N_{i-1}$.
If $A_i < 0$ then $P_i = A_i N_{i-1}$ and $N_i = \min(A_i, A_i P_{i-1})$.

If $\max(P_1,\ldots,P_n) > 0$, then this is the answer. The only way in which this fails to happen is if there is no subsequence whose product is positive. This can only happen if the array contains only negative numbers and zeroes, and every two negative numbers are separated by at least one zero. If there is at least one zero, then the answer is zero. If there are no zeroes, then $n = 1$, and the answer is $A_1$.


Proof of equivalence of L0 and language accepted by made up machine I have a made up machine, which has the same definition as Turing machine, but the transition function and the step of computation of the machine. What would be the approach of the proof that the language accepted by this machine is (or is not) equal to L0 (recursively enumerable language)?

You need to show that any language that is accepted by a Turing machine is accepted by one of your machines. So, start with an arbitrary Turing machine $M$ and show that one of your machines can accept $L(M)$, e.g., by showing how to directly simulate the operation of $M$.


Question about handwritten numbers recognition with limited data set I have a an assignment to make a classifier for hand-written numbers with a limited data set of 500 samples.
I am currently using python, I tried sklearn SVC with linear classifier and I got an accuracy of about 80%. I also tried KNN with 13 neighbors and got a max of 81% accuracy.
I need to get to at least 90% accuracy. What are your suggestions that would help with training (adding noise? what distribution? / tilting the pictures with 90 degrees? Maybe cross validating over different parameters... etc).

Edit:
To clarify the main challenge:
I have to reach an accuracy of more that 90% with only using 500 samples, I can play around with the samples however I want to extend the data but I am not allowed to use external samples.

I suggest you the following:

Adding a little bit of noise such as blurring
Transforming the images. You can rotate or stretch a bit, but make sure you don't change too much to change 6 to 9 or o to 0.

You can look at the following tutorials:

https://stackoverflow.com/questions/14177744/how-does-perspective-transformation-work-in-pil
http://opencv-python-tutroals.readthedocs.io/en/latest/py_tutorials/py_imgproc/py_geometric_transformations/py_geometric_transformations.html
http://effbot.org/imagingbook/image.htm


Is it possible to train a neural network to solve NP-complete problems? I'm sorry if the question is not relevant, i have tried to search for articles about it but i couldn't find satisfying answers.
I'm starting to learn about machine learning, neural networks etc ... and i was wondering if making a neural network that takes a graph as input, and output the answer of an np-complete problem (e.g. the graph is hamiltonian / the graph has independant set superior to k, and other decision problems) would work ?
I haven't heard of any np complete problems being solved like this, so i guess it does not work, are there theoretical results stating that a neural network cannot learn np-complete language or something like this ?

To answer your question, I would to point you to the field of computational learning theory (CLT), which applies complexity theoretic approaches to analyse machine learning.
An important concept in CLT is probably approximately correct (PAC) learning: in simple terms, a problem is PAC learnable if there exists an efficient algorithm which learns the data using a polynomial number of samples from the underlying distribution of the problem with an (polynomially small) error of $\epsilon$ and (polynomially small) failure probability $\delta$.
Unfortunately, there is a big disconnect between results in CLT and results in applied machine learning, so you are unlikely to find result proving or disproving the learnability of NP complete problems using deep neural networks as it is still an active area to research.
Here are some resources to computational learning theory:

Wikipedia: https://en.wikipedia.org/wiki/Computational_learning_theory
The original paper on CLT by Leslie Valiant: http://web.mit.edu/6.435/www/Valiant84.pdf
The hardness of training a particular neural network is NP complete: https://people.csail.mit.edu/rivest/pubs/BR93.pdf
Very good set of notes on CLT:

https://www.cs.ox.ac.uk/people/varun.kanade/teaching/CLT-HT2018/lectures/lecture01.pdf
Section 3 defines and gradually introduces the concept of PAC learning

Section 5.1 of these notes show how 3-COLOURABILITY can be phrased in the PAC learning framework:
In Section 5 as well, the notes show how "3-TERM-DNF is not efficiently PAC learnable (take II) unless RP = NP"


What are the units for time complexity graphs? I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one:

I know the x-axis represents some amount of information, and the y-axis represents some amount of time. However, what is the amount of actual time or data represented, does it depend on different types of computers or is it a standard (e.g.) bytes to seconds or KB to minutes?

We use Big-O notation to describe how "fast" an algorithm runs with respect to the size of the input in the worst case scenario. This input can be a number, a list of numbers, a matrix, etc. By fast, it essentially translates to number of steps the algorithm takes based on the size of the input in the worst case scenario.
I should start by describing the difference between an algorithm and an implementation of an algorithm. An algorithm is just a set of instructions that solves a problem. An implementation of an algorithm is code that is run on hardware that actually performs the set of instructions.
Suppose we have a simple problem, "given a list of numbers of arbitrary size and in no particular order, find the maximum value in the list". We solve this problem with an algorithm. Below is a solution to the problem.
FindMax(ls)
   m <- null
   for each x in ls
      if x > m
         m <- x

   return m

To analyze how good this solution is, we to find what the worst case is for this algorithm to handle. For this algorithm, the worst case would be a sorted list in ascending order. This is because the if statement will always be true (adding more steps).
Let $n$ be the size of the input list. Now let's count the number of steps our algorithm takes to complete (in the worst case). The initialization is 1 step (m <- null). The for loop will loop $n$ times. The amount it does inside the loop will be 2 steps (1for the if statement check and 1 for its body). Finally, 1 step for return m.
Let $T(n)$ be the worst case runtime for our algorithm. From above we have $T(n) = 1 + 2*n + 1 = 2*n + 2$.
This is where big-O notation will help us. We need to find a function $g(n)$ grows at a similar rate as $T(n)$; this function will be our upper bound. In other words, we need to find a function $g(n)$ where $T(n) \leq k*g(n)$ for all $n \geq n_0$.
Let's try $g(n) = 1$. Here we see that no matter what $k$ we try, $T(n)$ will always be greater at some point; more precisely, when $n>k$ then $T(n) > k*g(n)$. This means $g(n) 1$ is not big enough.
Let's try $g(n) = n$. Here we see that if we choose $k \geq 3$ and $n_0 = 1$, $k*g(n) \geq T(n)$ for $n \geq n_0.
What we proven is that $T(n)$ is bounded above by $g(n) = n$. This means that $T(n) \in O(g(n))$; in other words $T(n) \in O(n)$. Notice how I used $\in$ instead of $=$. This is because $O(g(n))$ is the set of all functions that are bounded above by $g(n)$. However, it is common practice to abuse the notation $T(n) = O(n)$.
The purpose of this example is to show you the context of big-O notation. Big-O notation is purely abstract in that we count the number of steps of the algorithm, not the amount of time (in seconds) it takes to complete. If we implement this algorithm in a program language (like C/C++ or Java) and run it on the computer, then we have many more factors to consider:

Number of cores of CPU
Clock speed of CPU
Amount of memory
I/O speed of the input
Language specific performance issues (e.g. C/C++ faster than Java)
etc.

None of these factors describes how well an algorithm performs; rather they show how well the implementation performs. See Big O Notation for an example and more information.


Inorder tree tranversal on binary search tree doesn't give the elements in order? I have been told that inorder tree tranversal of binary search trees returns the tree elements in order. I came up with this binary search tree:

      20
    /
 10
    \
     26

However the inorder tree tranversal of this seems to be 10, 26, 20?! What is wrong here?

This is not a valid binary search tree, since 26 is greater than 20 and is in its left subtree.


Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem I recently came across the sentence in the Book Introduction to Algorithms section 4.1 The maximum sub-array problem:

We still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days.

Here $n$ is the number of days taken as an example to show the changes in price of stock.
We can consider this is the size of an array A.
Where we are provided with an Array A and we need to find the net change is maximum from the first day to the last day.

To explain more specifically it means for an array $A$ of size $n$ we need to check $\binom{n-1}{2}$ subarrays.

But, I cannot understand how we need $\binom{n-1}{2}$ sub-arrays?
If we take an array of size 5 could someone please explain to me why we need only 6 sub-arrays.
Won't the sub-arrays be:
[1...5]
[1...4]
[1...3]
[1...2]

[2...4]
[2...5]

[3...5]
[4...5]

Please correct me if I am wrong.
References: Maximum Subarray Problem

Thank you.

You have found a bug in one of the most famous textbooks on computer science!

While there are $n$ days, there are only $n-1$ changes in price of stock. So there are $\binom{n-1}{2}$ subarrays of the array of the changes in price of stock, assuming that a subarray starts and ends at different indices.
That explain away, I believe, why the books says "we still need to check $\binom{n-1}{2} = \Theta(n^2)$ subarrays for a period of $n$ days".

However, in fact, you are right that we still need to check $\binom n2$ subarrays.
Let $B$ be the array of the daily prices for a period of $n$, starting at index (day) 0. Let $A$, as in the book, be the corresponding array of the price changes, starting at index (day) 1. If you select to buy on day $i$ and sell on day $j$, making a profit of $B[j]-B[i]$, it corresponds to subarray $A[i+1\,..\,j]$, i.e., $(A[i+1], A[i+2], \cdots, A[j])$. Please note the change of indices from $i$ and $j$ in $B$ to indices $i+1$ and $j$ in $A$. While $i$ and $j$ must be different always as "you are allowed to buy one unit of stock only one time and then sell it at a later date", $i+1$ and $j$ are the same when $j=i+1$, i.e., when you sell the next day.
Let us verify the sum of selected numbers in $A$ is indeed $B[j]-B[i]$. $$\begin{aligned}
&\quad A[i+1]+A[i+2]+\cdot+A[j]\\
&=(B[i+1]-B[j])+(B[i+2]-B[i+1])+\cdot+(B[j]-B[j-1])\\
&=B[j]-B[i].\end{aligned}$$
Note the formula does hold when $j=i+1$.
Besides the subarrays of $A$ that start and end at different indices, we must consider the subarrays with the same starting index and ending index. There are $n-1$ of them, i.e., the subarray whose only element is $A[1]$, the subarray whose only element is $A[2]$, ... and the subarray whose only element is $A[n-1]$. Since $\binom{n-1}2+(n-1)=\binom n2$, we still need to check $\binom n2$ subarrays.
For example, if the daily prices for a period of $3$ days are $B=(85, 105, 102)$, the changes of prices are $A=(20, -3)$. If we do not check the subarray of $A$, $(20)$, which stands for buying at price $85$ on day $0$ and selling at price $105$ on day $1$, we will miss the optimal profit, $20$.

This simple and obvious bug is not listed on the errata page for Introduction to Algorithms, Third Edition. It is incredible that this bug has been living comfortably in that popular book for over ten years before you pointed out explicitly.
On the other hand, many people might have been aware of that bug, although I did not notice it. The focus of that mistaken statement is "we still need to check $\Theta(n^2)$ subarrays for a period of $n$ days". The actual number of subarrays that should be checked is not that critical, as long as its level of asymptotic growth is correct. While misleading otherwise, that bug does not harm much the development of a better algorithm.


Optimising an exhaustive search for a card game I'd like to search for a combination of resources that when used, would produce at least up to a threshold of different kinds of materials. For the majority who are not in the know, I'll use an analogue for the rest of the question. For the few who benefit from this information: the game I'm referring to is Magic The Gathering, and the problem is finding whether or not a set of lands can cast a given card.
We can think of the materials as steel and wood. Any resource produces a combination of them. For example:
Requirement: 1 steel + 2 wood
Resources:
- 1 steel + 1 wood
- 1 wood
Verdict: POSSIBLE

There may be generic requirements, which can be fulfilled by whatever resource is available.
Requirement: 2 ANY + 1 wood
Resources:
- 1 steel
- 1 wood
- 1 wood
Verdict: POSSIBLE

Resources may be used to produce different combinations at will, when stated of course.
Requirement: 1 steel + 1 wood
Resources:
- 1 steel
- 1 steel OR 1 wood
Verdict: POSSIBLE

Finally, there may be costs associated with certain production. Here marked as cost -> production. Costs are production specific.
Requirement: 2 steel
Resources:
- 1 steel
- 1 wood
- 1 wood -> 1 steel OR 0 -> 1 wood
Verdict: POSSIBLE

Now, given a set of these resources it is relatively easy to figure out if a given requirement can be fulfilled. What I have currently is a naïve exhaustive search with one optimisation (step 1). In pseudo-python it goes as follows:
1. produce with resources that have only one production and no cost to have current "production"
2. can_fulfill(requirement, current production, resource list)

def can_fulfill(requirement, production, resources):
    for i, resource in enumerate(resources):
        remaining = resources[:i] + resources[i + 1:]
        for cost, gain in resource:
            if can_subtract(production, cost):
                new_production = production - cost + gain
                if fulfilled(requirement, production):
                    return True
                recur = can_fulfill(requirement, new_production, remaining)
                if recur:
                    return True
    return False

It does work, and for single-production resources it is lightning fast. But in this particular case there can be many resources with multiple production options, which slows the calculation. I think the exhaustive search is my only option, because one can't know which productions ultimately lead to the fulfillment of a requirement, but could there be more clever optimisations I could implement?
My parameters are somewhat conservative for these kinds of optimisation problems I think: I expect to have up to twenty resources, each with up to eight - typically three different productions. In the game there are five production types (steel, wood and 3 more).

I suspect this may be NP-hard in general but probably feasible to solve efficiently in practice for the parameter sizes you discussion.
I will suggest an approach based on comments from j_random_hacker.  One plausible approach is to express this as an integer linear programming problem.  Let $a_{im}$ be the amount of material $j$ you have after the $i$th step of applying sources, $b_{ir} = 1$ if you apply resource $r$ in the $i$th step or 0 otherwise, and then write constraints to express that each step obeys the rules you've followed.  See Express boolean logic operations in zero-one integer linear programming (ILP) for some general techniques for that.  For instance, you'll have a requirement that $a_{im}\ge 0$ for all $i,m$; that $\sum_i b_{ir} \le 1$, that $\sum_r b_{ir} = 1$; and so on.  If you have a resource that contains multiple alternative combinations, treat each as its own resource and then add a constraint that if you pick one of those combinations in any step you can't pick any of the others ($\sum_i \sum_{r \in R} b_{ir} \le 1$, where $R$ is the set of all combinations associated with a single resource).  If resource $r$ is "1 wood -> 1 steel", then we'd obtain a rule like
$$b_{ir}=1 \implies\\ (a_{i-1,\text{wood}} \ge 1 \land a_{i,\text{wood}} = a_{i-1,\text{wood}} - 1 \land a_{i,\text{steel}} = a_{i-1,\text{steel}}+1).$$
Then, convert that to an ILP constraint using the techniques at the link above.
Finally, you can apply an off-the-shelf ILP solver to search for a solution.
Note that the order in which you applies resources matters, because you can never go negative on any material, which complicates the ILP instance a little bit and requires you to have a separate copy of each variable per step.

If you prefer to adjust your exhaustive search, there may be ways.  One possibility is to use branch-and-bound to prune off some parts of the search space.  At any intermediate point in your search, you can get a simple bound on whether it's possible that a solution could exist from here by picking a single material, say wool, counting how many wool you already have, counting how much more wool you could possibly make if you used every remaining wool-producing resource to produce the maximum amount of wool (assuming optimistically all its preconditions can be met), and checking whether that would give you enough wool to meet the target.  If not, then there's no point continuing the search from here; you can prune the search.  Another way to get a simple bound is to look at the total number of materials, ignoring their type (e.g., total amount of mana, ignoring color); then using each resource that you haven't used so far that increases the number of mana (assuming optimistically that it can be used), and check how much mana total that would give you; if that's not enough for your target, then you can prune the search.
However, ILP solvers already use branch-and-bound, and they are probably doing something that generalizes  this and is more powerful.  So, rather than implementing branch-and-bound yourself with some limited set of bounds, I suspect it might be more powerful to use a full ILP solver.


Indentations in If-Else? I am a beginner at Java and this code example came up in class:
int horsepower = 15;
      if(horsepower > 15)
         if(horsepower <= 20)
            System.out.println("There is a lot of horsepower");
      else
          System.out.println("The car super fast");

the output is nothing but I can't understand why.
I have 2 questions I would like to clarify:

why did the code under the else statement not get executed?
I understand that without the brackets { }, the if condition can only execute the next statement. In this case, if horsepower variable is 17 instead, will "There is a lot of horsepower." be printed ? I am unsure if the System.out.println("There is a lot of horsepower"); still qualifies as being part of the next statement of the first if condition.

Please advise. Thanks!

Indentation has absolutely no syntactic or semantic meaning in Java, and indeed in most popular languages (the main exception is Python).
Which if does your else belong to? This is an instance of the famous dangling else problem.
The syntax of Java associates each else to the innermost if, so the Java compiler understands your code in a way which is different than what your indentation suggests. If you want to associate the else with the outer if, you can use curly brackets.


Runtime difference bewteen Union by Rank and Union by Size for union-find I was studying Union Find, and according to Wikipedia, there are 2 types of union: union by rank and Union by size. My question is, what is the runtime difference between the two (if any)?
Intuitively, it feels like Union by size would always be better, since each time we merge, we are increasing the rank of every node in one tree by 1, and to minimize overall runtime, we want to increase that one tree to be the one with smaller number of nodes, even though the final tree height might be greater.
But does this make a big difference in runtime?

If you combine union by rank or union by size with e.g. path compression the amortized complexity is the same [$O(m\alpha(m,n))$]. But notice that Wikipedia uses union by rank in order to prove the upper bound $O(m\log^*(n))$ because for proof purposes the union by rank algorithm is simpler to handle. On the other hand if you are implementing such a data structure you usually want to allow the user to access the sizes of the sets in the structure and thus use union by size method in order to keep track of the sizes and don't waste space for an extra array.

Its worth mentioning if we don't combine them with e.g. path compression both work in amortized $O(log(n))$.

This is a good lecture on this topic. It contains references to all the papers proving bounds for the problem. It also contains explanation of what $O(m\log^*(n))$ and $O(m\alpha(m,n))$ mean.


Finding the minimum subset of intervals covering the whole set Suppose we have a set $A$ of pairs $(a,b)$ such that $a$ and $b$ are real numbers and $a < b$. What is the most efficient algorithm to find the smallest subset $B \subseteq A$ such that, for any value within the range of any pair in $A$, the value is also within the range of any pair in $B$.

I am currently considering setting $B$ equal to $A$ and, for each pair in $B$, if removing the pair still upholds the property of $B$ described above, remove it. However, I feel this algorithm is too inefficient. Is there a more efficient algorithm?

Here's an $O(n\log n)$ algorithm, which is optimal in the algebraic decision tree model by an easy reduction from element distinctness (map each element $x$ to the interval $(x,x+\epsilon)$). We follow Kaveh's outline. Stage 1 runs in $O(n\log n)$ time, so we focus on Stage 2.

Let $I$ be the set of intervals in $C = (a,b)$. Define the intervals $l=(a,a+\epsilon)$ and $r=(b-\epsilon,b)$, and consider the interval graph over $I \cup \{l,r\}$ (two vertices are connected if the corresponding intervals intersect). I claim that every path from $l$ to $r$ corresponds to a cover of $C$, and vice versa.

First, consider a path $P$ from $l$ to $r$. Suppose that $P$ doesn't cover some point $x \in C$. We prove by induction that all the intervals in $P$ are to the left of $x$, which leads to a contradiction since $r$ is to the right of $x$. Clearly $l$ is to the left of $x$. Suppose some $p \in P$ is to the the left of $x$, and let $p'$ be the next interval on the path. If $p'$ were to the right of $x$, then since $p$ and $p'$ intersect, $x$ would have been covered. So $p'$ must also be to the left of $x$.

For the other direction, order the intervals in a cover of $C$ in increasing order of their starting point. If two consecutive intervals $(a,b),(c,d)$ do not intersect then the point $x = (b+c)/2$ is not covered. Similarly, the first interval must intersect $l$. While it is not generally true that the last interval must intersect $r$, one of the intervals must, and if we cut the cover short at the first such interval, then we obtain another cover of $C$ which also constitutes a path in the interval graph from $l$ to $r$.

We have reduced the problem of covering $C$ to finding the shortest path in an interval graph. This is solvable in time $O(n\log n)$ and space $O(n)$, as shown for example in An Optimal Algorithm for Shortest Paths on
Weighted Interval and Circular-Arc Graphs with
Applications by Atallah, Chen and Lee.


Is there any language that can be Turing-reduced to all languages? I suppose not, but I do not have a clear way to prove it. Right now, I am trying to find a counter example that there exists a language that cannot be reduced from the language, but I am not sure if there is the right direction.

Every Turing-decidable language is Turing-reducable to every language.
According to the definition in Wikipedia,

Given two sets $A,B \subseteq \mathbb{N}$ of natural numbers, we say $A$ is Turing reducible to $B$ and write
$$A \leq_T B$$
if there is an oracle machine that computes the characteristic function of $A$ when run with oracle $B$.

Now if $A$ is decidable, the oracle machine can decide $A$ even without the use of the oracle, so $A$ is Turing-reducible to every language.


What does the algorithm calculate? We have the following

i <- 0
j <- 0
x <- 1
y <- 1
z <- 1
c <- 1
u <- 1
while i<n do
   i <- i+1
   j <- i
   x <- x*i
   z <- x
   y <- i+1
   y <- x*y
   while j<2*i do
      j <- j+1
      z <- z*j
   od
   c <- z div (x*y)
od

I want to find the loop invariant for both while-loops.

I applied the algorithm some times to understand what it does:

The inner while loop calculates the following: $$z=z\prod_{m=1}^{2i-1}(i+m)=x\prod_{m=1}^{2i-1}(i+m)$$ or not? Is this also the loop invariant of the inner while loop?

So I got the following results:

First loop:

i=1
j=i=1
x=1
z=x=1
y=i+1=2
y=x*y=2
inner while loop: z=x(i+1)=2
c = z div (x*y) = 2 div 2 = 1

Second loop:

i=2
j=i=2
x=1*2=2
z=x=2
y=i+1=3
y=x*y=2*3=6
inner while loop: z=x(i+1)(i+2)(i+3)=2*3*4*5
c = z div (x*y) = 2*3*4*5/2*6=10

Third loop:

i=3
j=i=3
x=2*3=6
z=x=6
y=i+1=4
y=x*y=24
inner while loop: z=x(i+1)(i+2)(i+3)(i+4)(i+5)=6*4*5*6*7*8
c = z div (x*y) = 6*4*5*6*7*8/6*24=5*7*8=280

Is everything correct? But what exactly calculates the algorithm? What is a general formula of the results?

Note that $x=i!$. Now it's easy to see $y=(i+1)!$ and $z=(2i)!$. So $c=\frac{(2i)!}{i!(i+1)!}$, which is the $i$th Catalan number.

P.S. Your formula is wrong. The condition of the inner loop is $j=i+m\le2i$, so $m$ is from $1$ to $i$ instead of $2i-1$ or something.


Examples for directed graphs with super polynomial cover time The cover time of a graph is the expected number of steps in a random walk on the graph until we visit all the nodes.

For undirected graphs the cover time is upperbounded by $O(n^3)$.
What about directed graphs? I'm looking for examples of super-polynomial cover time.

Is there an example for such graph with $O(2^{\sqrt n})$ cover time?

Yes, it's not too hard to construct such a graph.  Consider a path $v_1 \to v_2 \to v_3 \to \dots \to v_n$ containing $n$ vertices.  Now add a new "dead-end vertex" $w$, and add edges $v_1 \to w$, $v_2 \to w$, $v_3 \to w$, etc.

If you do a random walk starting at $v_1$, the probability that you reach $v_n$ is $1/2^{n-1}$, as you have to get lucky and move in the right direction at each of the vertices $v_1,\dots,v_{n-1}$ to avoid getting stuck at the dead end.  Therefore, the cover time will be $\Omega(2^n)$.

Notice how things would change if we converted this into an undirected graph.  In an undirected graph $w$ would no longer be a dead end: if we hit $w$, we're not stuck (we still have a chance to get back to where we want to be, by backtracking our steps).  In the directed graph, $w$ is a dead end: once you hit $w$, you're done and you have no hope of making it to where you want to be.


How to prove that this is NP complete? I'm trying to prove that if P = NP, then {⟨a, b, c⟩ : a + b = c} (as addition over N) is NP-complete.

I think I managed to prove that it is in NP, but I'm not sure what would be a good NP complete problem to reduce to would be, or what algorithm to use. Any ideas?

Your language is in P; try to figure out why. If P=NP, all non-trivial languages in P are NP-complete, and in particular this one.


Inserting a sentence into search trees Let's say you have the following sentence: "This is my first cs question posted here". How would I go about inserting the sentence into a search tree. Do I assign each word a number value and perform the insertions based on those?

Search trees of various sorts can work with an arbitrary ordered domain, as all they rely on is a comparison function which is assumed to satisfies the axioms of a complete order:

If $a < b$ and $b < c$ then $a < c$.
Exactly one of $a < b$, $a = b$, $a > b$ (shorthand for $b < a$) holds.

In your case, you're probably meant to use the lexicographic order on strings. In this order, $x < y$ if:

Either $x$ and $y$ first differ in the $i$th symbol, and $x_i < y_i$;
Or $x$ is a prefix of $y$.

Symbols are probably compared in ASCII order in your case.


How to prove that existence of one-way functions implies P≠NP? Wikipedia:

The existence of such one-way functions... would prove that the complexity classes P and NP are not equal.

How is this proved?

Suppose that P=NP, and that $f\colon \{0,1\}^* \to \{0,1\}^*$ is an arbitrary function computable in polynomial time. Suppose that $|x| = n$, and we are given $y = f(x)$. We will show how to find $z \in \{0,1\}^n$ such that $y = f(z)$ in polynomial time (in $n$).
Using an NP oracle, we determine whether there exists $z$ such that $z_1 = 1$ and $y = f(z)$. If so, we set $w_1 = 1$, and otherwise, we set $w_1 = 0$. Using an NP oracle, we determine whether there exists $z$ such that $z_1 = w_1$, $z_2 = 1$, and $y = f(z)$. We set $w_2$ accordingly. Continuing in this way, we eventually found $z$ such that $y = f(z)$. Since we assumed that P=NP, this algorithm runs in polynomial time.


Why can't we exploite finiteness to prove incompleteness in NP? It is well established that the class of recursive languages is strictly contained in the class of recursively enumerable languages (Rec $\ne$ RE). Any finite language is decidable and hence can not be RE-complete. My intuition is that an RE-complete language contains infinite number of (finite) strings (information) and can not be reduced to a finite language.

The situation is different for the class NP since we can not rule-out finite NP-complete languages. If P=NP then there is some finite NP-complete language (under Karp reduction).

  Is there an intuition (or evidence) that explains why finite languages can not be complete for NP?

I am looking for an intuition (evidence) that supports the conjecture that all NP-complete languages must be infinite (It should not assume anything about P vs NP). Different notions of completeness inside NP may have significant impact on the properties of complete languages inside NP.

This was moved from a comment. Finiteness of complete languages shifts the focus on using the right notion of reduction to define completeness inside NP. The following post on CS Theory shows that defining completeness using injective Karp reductions would prove $P \ne NP$. The reason is  that SAT is infinite language and can not be reduced to a finite language using injective Karp reductions.

Here is a good reason why finiteness does not help: Let $P_{inf}$ and $NP_{inf}$ be the sets of infinite languages in $P$ and $NP$. Then we may focus on proving $P_{inf}\not=NP_{inf}$, rather than $P\not=NP$. But $P_{inf}=NP_{inf}$ if and only if $P=NP$!

The question as I understand it is, why can't we exploit the fact that these languages are finite in a proof of $P\not=NP$, like we did when we proved $R\not=RE$? But the premise is wrong: the proof that $R\not=RE$, that the Halting Problem is undecidable, does not reference the fact that there are finite languages in $R$. Of course it makes intuitive sense that, since $R$ contains finite languages, it cannot contain $RE$, but in fact $R\not=RE$ follows from the fact that Turing Machines cannot be analysed by other Turing Machines, and, in my view, the fact about finite languages is a quirk which follows from the definitions, as we may as well have considered $R_{inf}\not=RE_{inf}$.

If $R\not=RE$ comes from the fact that undecidability cannot be eliminated, then $P\not=NP$, if true, comes from the fact that nondeterminism cannot be efficiently eliminated.

I should clear up some technicalities. If a language contains a finite amount of strings, it can be decided in constant time, $O(1)$, so it is definitely in P, as you note. If P=NP, then every language in P is also NP-Complete (the reduction is simple: given a string, solve it in polynomial time, and then print a fixed yes/no instance of the other problem). So not only is there some finite NP-Complete language, all nontrivial* finite languages are NP-Complete if P=NP. On the other hand, if $P\not=NP$, then no finite language is NP-Complete. Your intuition about RE-Complete languages containing infinite strings is wrong: those languages contain an infinite number of finite strings.

*A nontrivial language is one with both yes- and no-instances. The two trivial languages are the empty language $\emptyset$ and the full language $\Sigma^{*}$, which have no yes- and no no-instances, respectively, which is why no other language can many-one reduce to them.


Is this grammar LL(1) grammar? Is this grammar LL(1)? Would it be a problem that S can be both E/S and E?

S -> E / S
S -> E
E -> letter
E -> ‘ S ’

Can it derive ‘a / e / ‘g / s’ ’ / q like this?

S - >  E / S
S - > ‘S’ / S
S - > ‘E / S’ / S
S - > ‘a / S’/ S
S - > ‘a / E / S’ / S
S - > ‘a / E / ‘E / S’’ / S
S - > ‘a / e / ‘g / s’’ / q

Plugging it into my LL(1) computer, loner gives false:

<S> ::= <E> | <S>;
<S> ::= <E>;
<E> ::= 'letter';
<E> ::= '"' <S> '"';

(Note there are some duplicate rules here, which become apparent in the formatted version.)

Proving it (e.g., via the set properties or a pumping lemma) is left an exercise.

If / is intended to a be terminal (and not alternation!), then we have

<S> ::= <E> '/' <S>;
<S> ::= <E>;
<E> ::= 'letter';
<E> ::= '"' <S> '"';

is still not LL(1).

The derivation would be more readable (and more obviously correct) if shown like (e.g.)

S ->  E / S
(with E -> 'S')
-> 'S' / S
(with S -> E / S)
-> 'E / S' / S
(with E -> letter)
-> 'a / S'/ S
(with S -> E / S)
-> 'a / E / S' / S
(with S -> E -> 'S' -> 'E / S') ; note the application of several steps, here
-> 'a / E / 'E / S'' / S
(with S -> E -> letter) ; and again. better to be explicit
-> 'a / e / 'g / s'' / q


Turing machines moving left at least once Is the following language decidable?
  $$ L = \{ \langle M,w \rangle \mid \text{$M$ moves its head left at least once when run on $w$}\}. $$

I feel like this is a decidable language. But I don't know the algorithm to prove that it is decidable. Any help would be appreciated.

Let's assume for simplicity that at each step, the head moves either left or right (but doesn't stay in place).

Suppose that $M$ never moves its head left when run on $w$.
After the machine traverses the length of $w$, it reaches a blank cell, and from this point on, will always fall on a blank cell. Therefore the only information that changes from step to step is the current state of the machine. After at most $|Q|$ steps (where $Q$ is the set of states), the machine will either halt or repeat a state, in which case it enters an infinite loop.

This gives a simple algorithm for deciding your language, that I'll let you spell out.

If the head is also allowed to stay put, the argument becomes a bit more complicated, but the conclusion is identical.


Problem with derivative of sigmoid activation function I'm following Jeff heatons book 'Introduction to Neural Networks with Java'.
To get node deltas, we need to calculate $f'(sum)$. In the very first row for Training Element #1, we need to compute $f'(1.13) \cdot 0.25$ which Heaton evaluates to $0.045$.

Using my calculator, I get $f'(1.13)=-0.13$ (derivative of sigmoid activation function), then I multiply by $0.25$ to get $-0.0325$. I've been trying to figure out for days how heaton does his calculation but no success yet. Kindly assist.

The derivative of a sigmoid is always positive.  Here's my math: Sigmoid(1.13) = 0.7558

I computed this on Wolfram Alpha

The derivative of a sigmoid y=S(x) is y * (1-y), so 0.7558 * 0.2442 = 0.0451


Why isn't plus_assoc rewriting correctly? First I have plus_assoc ready.
Theorem plus_assoc : forall n m p : nat,
  n + (m + p) = (n + m) + p.

for simplicity we omit the proof of plus_assoc.
now I want to prove plus_swap:
Theorem plus_swap : forall n m p : nat,
  n + (m + p) = m + (n + p).
Proof. intros n m p. rewrite -> plus_assoc. ...

the equation was rewritten into n + m + p = m + ( n + p ),  rather than the expected (n + m) + p = m + (n + p). why?

It is rewriting correctly. Coq doesn't print redundant parentheses. The + operator is left-associative, so n + m + p is a valid way of writing the term (n + m) + p, and Coq prints it without the parentheses.
Coq < Check (n + m) + p.
n + m + p
     : nat

Just to be clear, n + m +p and (n + m) + p are exactly the same term, not just terms that are equal. They're different ways to use notations to write Nat.add (Nat.add n m).
Theorem plus_swap : forall n m p : nat,
  n + (m + p) = m + (n + p).
Proof.
  intros n m p.
  Unset Printing Notations.
  Show. (* Now the goal is shown as: eq (Nat.add n (Nat.add m p)) (Nat.add m (Nat.add n p)) *)
  rewrite -> plus_assoc. (* Now the goal is: eq (Nat.add (Nat.add n m) p) (Nat.add m (Nat.add n p)) *)


n mod 4 asymptotic analysis best case and worst case if 0==(n mod 4) then
  do somthing ϴ(n^2)

else if 1==(n mod 4) then
  do somthing ϴ(n^3)

else if 2==(n mod 4) then
  do somthing ϴ(n^4)

else if 3==(n mod 4) then
  do somthing ϴ(n^5)

what is best case and worst case for this algorithm?

Best case and worst case are about the complexity for a fixed input length. As an example, suppose we are sorting an array of length $n$. There are many possible arrays of length $n$. On some of them the algorithm will be faster, on some it will be slower.

In your case, in contrast, the running time doesn't depend on the input, but only on its length. Therefore the best case and the worst case are both
$$
\begin{cases}
\Theta(n^2) & \text{if } n \equiv 0 \pmod{4}, \\
\Theta(n^3) & \text{if } n \equiv 1 \pmod{4}, \\
\Theta(n^4) & \text{if } n \equiv 2 \pmod{4}, \\
\Theta(n^5) & \text{if } n \equiv 3 \pmod{4}.
\end{cases}
$$


Number of rooted labelled trees According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2

If the tree is rooted then in each tree we can choose a root in n ways so total number of rooted labelled trees is n^n-1.

Here when computing the total number for rooted labelled tree, why don't we consider the ordering of elements ?

For example if we have a regular graph with 3 vertices then one of the spanning tree is 1->2->3. Here each element can be root and we can have remaining elements at right or left. So why don't we consider the ordering (right or left) in the formula?

We don't consider the order of elements since what we are counting is the number of graphs on the vertex set $\{1,\ldots,n\}$ which are trees, that is, connected and having no cycles.

This is the usual graph-theoretic notion of tree. In computer science we often think of trees as rooted objects with ordered children, which is a similar but different concept.


Why the most dominant programming languages didn't follow CSP thread model? I was trying to ask this question in StackOverflow, but later realized that this question is more relevant to general computer science, not specific engineering problems. If you think it's not, please let me know.

Recently I've found out what CSP(Communicating Sequential Processes) is.
According to the article Bell Labs and CSP Threads:

Most computer science undergraduates are forced to read Andrew Birrell's “An Introduction to Programming with Threads.” The SRC threads model is the one used by most thread packages currently available. The problem with all of these is that they are too low-level. Unlike the communication primitive provided by Hoare, the primitives in the SRC-style threading module must be combined with other techniques, usually shared memory, in order to be used effectively...

Another article Share memory by communicating from Golang blog says:

Traditional threading models (commonly used when writing Java, C++, and Python programs, for example) require the programmer to communicate between threads using shared memory (...)
Go's concurrency primitives - goroutines and channels - provide an elegant and distinct means of structuring concurrent software. (These concepts have an interesting history that begins with C. A. R. Hoare's Communicating Sequential Processes.)

Based on what I've seen so far, because Hoare proposed CSP in 1978, it seems that there was no reason to use SRC thread model in programming languages like C++(1985), Java(1995) or Python(1990).
So my question is, why the most dominant programming languages didn't follow Hoare's thread model?
Here's my guesses:

Most programmers back then didn't know about Hoare's thread model.
Most programmers are used to traditional thread model.

What do you think?

There are many approaches for concurrency, with different tradeoffs.  We have threads with shared mutable state (e.g., SRC-style threading).  We have coroutines (like Go).  We have actor models with independent processes communicating via message passing (like Erlang or E).

I would put CSP on a different level.  It's not the same sort of thing.  The form of CSP that I am familiar with is a mathematical, theoretical formalism that can be used to model concurrent systems.  It's not really a model of programming that can be directly used in programming languages.  It's more like the lambda calculus.  You can build programming language APIs inspired by CSP, just like Lisp and Scheme are inspired by the lambda calculus, but it's not directly a design of a thread API itself.

Why did early languages choose to follow the SRC model rather than something inspired by CSP?  Well, all I can share with you is speculation.  The SRC model is a low-level model that maps pretty closely to the primitives provided by processors: it is a thin level of abstraction over that.  Just like C is a thin layer over assembly language (and doesn't use, say, functional or declarative paradigms), it's not surprising that early languages would provide a thin layer over processor primitives (rather than, say, other theoretical paradigms).  Also, the SRC model works well with existing code and existing programming languages.  You can take existing sequential code and then add threads.  When you're writing threaded code, the sequential part of the computation looks just like code written for a non-threaded language.  That backwards compatibility and familiarity was probably significant.  The SRC model could be deployed as a library, without requiring changes to programming language syntax or compilers.  I have to imagine that might have been a significant factor in its adoption.  Also, the SRC model is somewhat similar in many ways to existing Unix primitives for running code in parallel in multiple processes, which I imagine might also have been beneficial for adoption.  This is just my speculation.  Perhaps someone else will be able to provide a more researched answer.


Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language? I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable but not recursive just like the Halting Problem, but is it enough to say that if I can solve the Halting Problem then I can solve $L$, because then I can feed into the Halting Problem the input $w_i$ twice, as both input and Turing machine encoding?

Do I need to reduce it to the diagonalization language instead?

I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable

So far, so good.

  but not recursive just like the Halting Problem

Here we have a problem. Reducing $L \leq_m HALT$ does not prove that $L$ is not recursive. Actually, all recursive languages reduce to $HALT$!

  but is it enough to say that if I can solve the Halting Problem then I can solve $L$

No, this is not a may-one reduction argument. Indeed, if you can solve $HALT$, then you can also solve its complement. This however, does not imply that the complement is r.e., otherwise we would get that $HALT$ is recursive.

You need to define a (total recursive) reduction function from $L$ to $HALT$.

Then you need to prove that $L$ is not recursive. For that, you could prove the opposite direction $HALT \leq_m L$, constructing a reduction function from $HALT$ to $L$.


Delete a range of keys in a binary search tree in better than $O(n\lg n)$? Obviously, the brute force method of:

DeleteRange(root, low, high)
    for n = low to high
        if n == root.key // key found
            return DeleteNode(root) // O(lg n) to delete
        elseif n < root.key // in left sub-tree
            root.left = DeleteRange(root.left, n, high) // recur into left sub-tree
        elseif n > root.key // in right sub-tree
            root.right = DeleteRange(root.right, n, high) // recur into right sub-tree
        else // root.key == null, key not found
            return null
   return root

would take $O(n\lg n)$ time. So is there any "smarter" way of deletion that would do the same thing with less complexity, perhaps pruning entire sub-trees at once? Assume that the deleted nodes are not needed and the only concern is with returning the root of a binary search tree where the nodes between the range of two keys are deleted.

You might be interested in a data structure called TeardownTree. It supports delete_range operation that works in $O(k + \log n)$ time, where $n$ is the initial number of items in the tree and $k$ is the number of items deleted (and returned to the caller). Full disclosure: I am the author.

I have to emphasize that the data structure does not support the insert operation, but is optimized for clone and delete_range. I have written up an informal description of the algorithm. With all the optimizations the code is now significantly different from that document, but it should be enough to grasp the idea.


NP hardness of partitioning a graph into two subgraphs Given a planner graph which it's vertexes have weights and an integer, W, this graph should be partitioned into two subgraphs which sum of weights for each subgraph becomes at least W.

I wanted to show this is np hard by reduction and I have used Max cut to show that (in max cut we have a graph with weights for edges and need to partition it's vertexes into two subgraph which the sum of weights of edges between these two subgraph, becomes at least K)

I'm not sure about how to change weights of edges in max cut to weights of vertexes in the new problem, I've considered for each vertex weight the max weight of edges which it is an endpoint for, and W=K, is this correct?? if not how to consider the weights for vertexes and W?? or another problem should be used?? I appreciate if anybody guides me by the reduction.

ps: please consider that we can not use partition since it says at least W not W, or subset sum.

I think you can in fact do this by showing a reduction from the Partition problem, as stated by Chapichap. Recall the direction of reduction that is needed to show a problem is NP-Hard. In general, it is okay if the problem you have is harder than the problem you are using to show hardness (in this case, the partition problem). This is because the reduction would from the partition problem to the given problem. For the partition problem, if we are given a set of numbers $S$, and we want to find a partition $S_1,S_2=S\setminus S_1$, we need to show how to construct a graph $G$ and a number $W$ such that the vertices of $G$ can be partitioned as described (where the sum of weights of the vertices is at least $W$) if and only if the set $S$ can be partitioned.

Consider the following reduction: Let $G = (V,E)$ be a graph where $V=S$. That is, for each number in $S$, create a vertex in $G$. The edge set seems irrelevant here, so we can let $E=\varnothing$. The weight of each vertex is equivalent to the number in $S$ to which it corresponds. Finally, let $\lceil W=(\sum_{x\in S} x)/2\rceil$. That is, $W$ is the sum of the weights of all the elements of $S$, divided by two.

Asking for a partition in $G$ such that each partition has total weight at least $W$ means asking for each partition to contain half of the total weight of the graph. To be thorough, consider the case where $\sum_{x\in S}$ is even. Then $W$ is exactly half of the total weight of all vertices in the graph, and so for each partition to have a total weight of at least $W$, each partition must have equal weight. Thus such a partition of the vertices is equivalent to an equal-sum partition of the elements of the original set. Now, consider the case where $\sum_{x\in S}$ is odd. In such a case, $S$ has no partition such that the sum of the partitions are equal. However, the way we constructed $W$ ensures that $2W = (\sum_{x\in S})+1$ and so it is impossible to partition the graph so that each partition has total weight at least $W$ (the existence of such a partition would imply that the total weight of the graph is strictly greater than $\sum_{x\in S}$, which is impossible).

Hopefully you can see from the above that $G$ has a partition into two subgraphs such that the sum of the weights of vertices in each partition is at least $W$ if and only if the original set $S$ had a partition of its elements into two subsets such that the sums of elements in each subset are equal.


Running time of recursive algorithm with geometric series What is the complexity of the recurrence $T(n) = 3T(\frac n2) + O(n)$?

So far I have:

$ O(n) \le cn$ for some constant $c$

Hence:

$$T(n) \le 3T(\frac{n}{2}) + cn$$

After a recursion:

$$T(n) \le 3(3T(\frac{n}{4}) + \frac{cn}{2}) + cn$$
$$= 9T(\frac{n}{4}) + \frac{3cn}{2} + cn$$

After another recursion:

$$T(n) \le 9(3T(\frac{n}{8}) + \frac{cn}{4}) + \frac{3cn}{2}+ cn$$
$$= 27T(\frac{n}{4}) + \frac{9cn}{4} + \frac{3cn}{2} +cn$$

The general term is:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \frac{\sum_{i = 0}^k{3^i}}{\sum_{i = 0}^k{2^i}}cn$$

For some $k$

Now:

$$\sum_{i = 0}^k{(\frac{1}{2})^i} = \frac{1}{1-\frac{1}{2}}$$
$$ = 2$$

Hence:

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + 2\sum_{i = 0}^k{3^i}cn$$

I do not know how to proceed from here.

This question is from Algorithms; Dasgupta, Papadimitriou, Vazirani; 1st Edition. Question 2.3 (a)

Thank you.

$$T(n) \le 3^{k}T(\frac{n}{2^k}) + \sum_{i = 0}^k{(3/2)^i} cn$$

The recursion will reach the base case when $2^k = n$ (i.e., $k = \log n$).
And it is common to suppose the base case is $T(1) = 1$ (or $T(1) = d \textrm{ for some constant } d$).

Then (please check the details),

$$T(n) \le 3^{\log n} + \sum_{i = 0}^{\log n}{(3/2)^i} cn = n^{\log 3} + 3cn^{\log 3} - 2cn = (3c+1) n ^{\log 3} - 2cn$$


Meaning of the Time Hierarchy Theorem Given two positive integers $c_1$ and $c_2$ such that $c_1 < c_2$, it's easy to prove that $n^{c_1}$ is $\mathcal{O}(n^{c_2})$ while $n^{c_2}$ is not $\mathcal{O}(n^{c_1})$. In general, for any functions $f(n)$ and $g(n)$ it is possible to determine which one (or both) is true, $f \in \mathcal{O}(g)$ or $g \in \mathcal{O}(f)$ using only definition of big-O notation. Thus it is not hard to see that TIME($n^{c_1}) \subsetneq$ TIME($n^{c_2})$ without using the Time Hierarchy theorem.

So, what is the meaning of the Time Hierarchy theorem and how and where can I use it?

You miss the meaning of the Time Hierarchy theorem, or perhaps of the classes TIME($n^k$) that you show.

It is indeed obvious that $O(n^k) \subsetneq O(n^{k+1})$, for instance. It is also clear that the set of Turing machines that run in time $O(n^k)$ is a strict subset of those that run in $O(n^{k+1})$.

However, it is not immediately obvious that the set of problems that can be solved by TMs in time $O(n^k)$ (i.e., the class TIME($n^k$)) is a strict subset of TIME($n^{k+1})$. For this much stronger statement, you need the Time Hierarchy Theorem. That is, you need to argue that there exists some problem that can be solved in time $n^{k+1}$ but not in time $n^k$. (Of course, this is just a special case of applying the theorem to polynomial running times.)


On FPTAS and many one parsimonious reductions We have two $NP$ complete problems $\Pi_1$ and $\Pi_2$. Suppose  $\Pi_1\rightarrow\Pi_2$ be a many one parsimonious reduction.

If $\Pi_1$ has an FPTAS then does $\Pi_2$ also have?
If $\Pi_2$ has an FPTAS then does $\Pi_1$ also have?

Regarding number 1: The reduction to 3-SAT in the Cook-Levin theorem is many-one and parsimonious. There's no FPTAS for 3-SAT unless $\mathcal{P=NP}$, yet any problem in $\mathcal{NP}$, including those with a FPTAS, reduce to it in the fashion you describe.
With respect to number 2: I don't know many problems with FPTAS's but I strongly suspect that, if you look through a few and the reductions that prove them to be $\mathcal{NP}$-complete, you'll quickly find a counterexample. That's because I don't see any connection between being able to count solutions and being able to approximate them.


Transition coverage for a DFA Let $G$ be a directed graph, with a single source node $s$.  I want to find a collection of paths that cover every edge of $G$ (i.e., every edge of $G$ appears in at least one of these paths), where each path must start at $s$.  The cost of a collection of paths is the sum of the lengths of the paths.

Is there an efficient algorithm to find the minimum-cost collection of paths?  This smells like it might be NP-hard to me (it sounds like a set cover problem), so I'm guessing not.  If it is NP-hard, are there any good approximation algorithms or heuristics for this problem?

This sounds a bit like some kind of network-flow problem.  Every collection of paths from $s$ to $t$ is an integral flow from $s$ to $t$, and every integral flow from $s$ to $t$ can be expressed as a union of paths from $s$ to $t$.  The difference is that (1) the objective function we are trying to minimize is different from the standard network flow problem, and (2) the starting point of each edge is fixed to $s$, but the ending point is not fixed.  So, I don't know if network flow like techniques would help.

Motivation: Suppose I have a DFA, and I want to find a testsuite that achieves full edge coverage.  A test is a word over the alphabet of the DFA; a testsuite is a collection of tests.  A transition is covered by this testsuite if there exists at least one test in the testsuite that causes the DFA to follow that transition at some point.  Suppose the cost of a test is its length, and the cost of a testsuite is the sum of the costs of the tests.

Then we can ask whether there is an efficient algorithm that, given a DFA as input, outputs a minimum-cost testsuite that achieves full transition coverage.  That's exactly the graph problem outlined above.

This is related to a well known problem with a conjecture due to Karpovsky and Moskalev [1] (I still believe is open) that at most V-1 paths are needed.  It is tied to conjector of Erdos, Goodman, and Posa [2].

If you want the state of the art today, I suggest doing a thorough reverse-citation search on [1].

[1] Karpovsky, M. G., and E. A. Moskalev. "Covering of edges of graph by a minimal set of paths." Discr. Math 58.2 (1986): 214. (This is in the "research problems" section)

[2] Erdos, Paul, Adolph W. Goodman, and Louis Pósa. "The representation of a graph by set intersections." Canad. J. Math 18.106-112 (1966): 86.


Computer Programs and lambda terms without normal form λ-calculus an ideal mathematical model in which to interpret programs. A program can be interpreted as a lambda term, and the term can have or not have a normal form. What role the terms without normal form play when analyzing programs?

A troublesome one unfortunately. When one goes to examine programs there are two main ways to do it

Operationally

This is the sort of obvious approach to analysing a program in the lambda calculus. We give a set of rules for what it means for one program to step to another and then go on to prove things about programs stepping. Here a step is one small tweak to the program. We continue to step until we end up at a value at which point no more steps are applicable. A value in the lambda calculus is just a lambda term.

Now the obvious impact of nontermination is that for any term there is no guarantee that there is a finite number of steps leading it to a value. We can prove useful theorems like "Either a term is a value or there is an applicable step" (a form of type safety) and "A term can only step to at most one unique value" (a corollary of the Church Rosser Theorem). These are all still useful results that justify statements like "there are unequal lambda terms".

Denotationally

Here we're trying to understand the lambda calculus by mapping each term to a particular mathematical object so that the mapping is coherent in some way. Mostly we want it so that $denote(e) = denote(e')$ if and only if $e = e'$. With this theorem in hand we can go on and prove things in the denotation equal and actually generate useful theorems about the lambda calculus.

Here nontermination causes some real pain. We can't just treat lambdas as "normal" math functions because normal math functions terminate. Instead we explicitly model nontermination by dedicating a specific element in our mathematical collection as what nonterminating programs denote to. Then we go on and prove a theorem along the lines that if $denote(e)$ gives that nonterminating object, then $e$ doesn't run to a value (runs to in the sense of operational semantics).

However the lambda calculus is a pain to denote for a much more fundamental reason though: recursion. The nontermination in the lambda calculus emanates from the fact that the lambda calculus is built on top of this sort of cyclical definition: a lambda term is a function from $A \to A$ where $A = A \to A$. This recursive definition gives us self-application eg $\lambda x. x\ x$ which gives us nontermination.

Building a denotation involves building a collection where $$A \cong A \to A$$ which is just absurd if $A$ is a set and $A \to A$ is the normal collection of set-theoretic functions!

Indeed proving that such an $A$ exists was the impetus for a large field in programming language semantics called "domain theory". Dana Scott constructed such an $A$ by cleverly defining $A$ with an ordering relation on it and restricting functions to be continuous with respect to that ordering operation. Even with this the proof is very technical (and cool).


Help Understanding the Type and Complexity of my Programming Task I'm working on a programming task that I, without good evidence, have a sneaking suspicion is NP-Complete. With that said, I would like confirmation on this if possible, as well as some suggestion for a way to approximate a reasonable solution. Lastly, if this problem is just some popular problem in disguise, I'd love to look more into that problem. I'll now describe my task.

I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position. To complicate things further, I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

Is there any practical way I can solve (approximate fairly accurately) this problem? The overall salary limit seems to make this a tricky problem.

Thanks a lot!

Divide this problem into two parts.

  I am attempting to design a program to optimize daily fantasy baseball rosters given certain information. The context here is that I will be designing rosters of players from various games that consists of 2 pitchers and one player that plays each other position. This is complicated by the fact that each player is assigned a salary relative to their perceived ability and there is an overall cap on how much salary can be used in total. This means I am dealing with restrictions in terms of making sure that I do not exceed the combined salary cap, while also making sure that I have players at each position.

This sounds like the 0-1 Knapsack problem where you have an overall salary cap and salary and importance of each player.

So from a list of all the players available in the market, form your personal roster using this concept.

Now coming to the second part of your question,

  I want to be able to pick a few players (1-5 or so) at each position as my favorites, and have control over what % of my teams they appear in. That is, if I make 50 teams, I'd like to be able to make it so that I can generate these teams by inputting a list like: Player X (pitcher) 5%, Player Y (First Base) 50%, and so on.

You have a personal roster at hand and each player has a percentage attached to him. Try a greedy strategy to distribute players.

Pardon my ignorance of baseball's rules but here is a simple example to help you out. Suppose you have 10 teams where each team has to have only one keeper (the guy who stands behind the players with the bats). You have to distribute Keeper X, Y and Z among the two teams. X has a 10% percentage chance, Y has a 90% chance, Z has a 10% chance. So sort the players according in ascending order according to weightage and put X in team 1, Y in team 2 and Z in teams 3 through 10. Similarly sort according to your criteria, and develop your own heuristic  to fill each position.


How can I find this code block's execution time t(n) and big O notation? Hello I am a CSE student and this question was in my homework.
double fact(long i)
{
if (i==1 || i==0) return i;
else return i*fact(i-1);
}

funcQ2()
{
for (i=1; i<=n; i++)
sum=sum+log(fact(i));
}

I thought it is O(n^2) but can the bottom function's log function call make it O(n^3)? I am not sure
Thanks in advance

fact(n) runs at $O(n)$.
So, each iteration of funcQ2 runs at $O(i)$, assuming log runs at constant time.
(There are several algorithms to calculate the log)
Then the question turns into calculating $\sum_{i=1}^n O(i)$, and the answer is $O(n^2)$.
Now suppose your log(n) runs at time $O(f(n))$.
Then the answer to your question should be $\sum_{i=1}^n O(f(i))$.
You should calculate that on your own as I don't know the $f$.


What is the level of the material contained in the book Data Structures and Algorithm Analysis in C++ (4th Ed) by Weiss? The question is pretty much explained in the title. I have the necessary discrete math background and would like to learn algorithms and data structures in the process (of coding) - so the book quoted in the title seems a good read. Since the author states clearly in the preface that the book is suitable for an advanced data structures course or a 1st year graduate course on algorithm analysis, my question seems answered already. But I guess my real question is how much material is contained in the book and how advanced it is, say compared to the following resources:

Two MIT graduate-level courses - Advanced Algorithms (http://people.csail.mit.edu/moitra/854.html) by Ankur Moitra and Advanced Data Structures (https://courses.csail.mit.edu/6.851/spring12/) by Eric Demaine.

PS: I want to become a C++ programmer (generically speaking) with a strong algorithm and data structures background. Not really sure what material I should dive into. Any suggestions on this are also very welcome!

Once I skimmed through a dozen of textbooks, looking for ones better explaining sorting and data structures (i.e. no graphs, string algos and so on).

Weiss was the best one according to my criteria. In particular, it describes more advanced techniques for hash tables, which are heart of most real use cases. Although even this book doesn't include Robin Hood hashing - learn it from Wikipedia pointers.

More info: https://www.quora.com/How-do-I-learn-data-structure-and-algorithm-in-C++-I-know-the-basics-by-myself-Can-you-suggest-any-e-books-for-me-to-use/answer/Bulat-Ziganshin

Another extremely important topic: https://www.quora.com/What-are-good-resources-to-learn-concurrent-programming-in-C++/answer/Bulat-Ziganshin


How can I reduce a product of transpositions? I'm looking for an algorithm to solve the following task:

Input: a set $T$ of transpositions; a permutation $\pi$ expressed as a product of transpositions from $T$
Desired output: express $\pi$ as the shortest possible product of transpositions from $T$.

In other words, the output should be a list of transpositions $\tau_1,\dots,\tau_k$ such that $\pi = \tau_1 \circ \dots \circ \tau_k$, $\tau_1,\dots,\tau_k \in T$, and $k$ is as small as possible.

Is there an algorithm for this that will be efficient in practice?

For example, if I were given (2,3)(0,3)(0,3)(2,6)(2,3)(2,6)(0,3) = (0623), I could reduce it to (2,6)(2,3)(0,3) = (0623).

I have come up with a few methods, based on the following properties:

The product of identical transpositions cancel. For example, (1,2)(1,2)(2,3) = (2,3).
Any product of the form (x,y)(y,z)(x,y) is equal to (y,z)(x,y)(y,z).
Any transpositions which share no elements commute. That is, (u,v)(x,y)=(x,y)(u,v).

I have three methods, based on these three properties:

One simple method is simply finding instances of (1). In the first example, (0,3)(0,3) appears as a product, so I may remove those transpositions.
Another method is finding instances of (x,y)(y,z)(x,y)(y,z), since this is equal to (y,z)(x,y)(y,z)(y,z) = (y,z)(x,y).
A third method is to recognize if identical transpositions are separated by disjoint transpositions. For example, (0,3)(2,6)(0,3) = (0,3)(0,3)(2,6) = (2,6).

Are there any other methods I am missing here?

I will explain some of the context in which this problem appears. Consider a graph G with labelled vertices. On each vertex lies a pebble, $p_i$. A transposition in the given product corresponds to selecting an edge in G and swapping the pebbles that are incident to that edge.

Therefore, a product of transpositions corresponds to a process of exchanging pebbles of edges, and the end result is a permutation of the pebbles on G which is described by the permutation given by the product of transpositions.

Hence, this process of boiling down a product of transpositions is an attempt to reduce the number of exchanges needed to achieve any permutation of pebbles on a graph G.

I suspect your problem is NP-hard, but if you need to solve it in practice, I recommend using a SAT solver to help you.

Algorithms

I suggest you solve this using a SAT solver.  The problem can be expressed in a fairly straightforward way as an instance of SAT, and then you can apply an off-the-shelf SAT solver.

Let's solve the following problem:

Input: $\ell \in \mathbb{N}$; a set $T$ of $m$ transpositions; a permutation $\pi$
Question: Does there exist a way to express $\pi$ as a product of $\le \ell$ transpositions?

We'll construct a way to solve this problem using SAT, then apply binary search over $\ell$ to find the optimal solution.

For simplicity, add the identity element to $T$.  Then we can replace "$\le \ell$" with "exactly $\ell$".  Now the question can be expressed in a rather straightforward way as a CNF formula.

In particular, introduce boolean unknowns $x_{i,\tau}$ (for each $i=1,2,\dots,\ell$ and each $\tau \in T$), with the intended meaning that $x_{i,\tau}=1$ means that $\tau$ is the $i$th transposition in the output sequence.  Also, introduce boolean unknowns $y_{i,j,k}$, where $y_{i,j,k}=1$ is intended to mean that the first $i$ transpositions in the output sequence map $j$ to $k$.  We add constraints:

For each $i$, we require that exactly one of the $x_{i,\tau}$ is 1.
We require that the product of the transpositions yields $\pi$, i.e., $y_{\ell,j,\pi(j)}=1$ for all $j$.
We require that the $x$'s and $y$'s are consistent, e.g.,

$$y_{i+1,j,k} = \bigvee_{\tau} y_{i,j,\tau^{-1}(k)} \land x_{i,\tau}.$$
We require that $y_{0,j,j}=1$ for all $j$ and $y_{0,j,k}=0$ for $j \ne k$.

Now feed this to a SAT solver.  This should be satisfiable if and only if there's a way to express $\pi$ as a product of $\ell$ transpositions from $T$.

Finally, use binary search on $\ell$, as mentioned above, to find the shortest possible way to express $\pi$ as a product of transpositions from $T$.

(There are many different ways to express this problem as SAT, and those choices might affect the performance of the SAT solver.  So, if you need to solve this in practice, you might experiment with different ways of encoding the constraints into SAT.)

Hardness

I suspect your problem is NP-hard.

Researchers have studied a natural generalization of this problem where the set $T$ is allowed to contain arbitrary permutations, rather than just transpositions:

Inputs: $\ell \in \mathbb{N}$; a set $S$ of permutations; a permutation $\pi$
Question: Is there a way to express $\pi$ as a product of $\le \ell$ permutations from $S$?

This problem is NP-hard, as proven in the following paper:

The Minimum-Length Generator Sequence Problem is NP-Hard.  S. Even, O. Goldreich.  Journal of Algorithms, vol 2, pp.311-313, 1981.

This problem remains NP-hard even if \ell is specified in unary (i.e., there is not likely to be an algorithm that is polynomial in the length of the output).  Subsequent work showed that the problem is PSPACE-complete if $\ell$ is specified in binary.  That's not the same problem as yours, because you have the extra condition that $T$ contains only transpositions, but it is related.

A subsequent paper showed that if $T$ generates a transitive group, then the problem is NP-hard.  In your case, this corresponds to the condition that the underlying graph be connected.  I suspect you're dealing with a connected graph (otherwise you can trivially decompose into connected components and the complexity will depend on the size of the largest connected component).  As a result, this appears to imply that your problem is NP-hard.

This hardness result is mentioned in Section 4 of the following paper:

The complexity of finding minimum-length generator sequences.  Mark R. Jerrum.  Theoretical Computer Science, vol 36, pp.265--289, 1985.

Assuming this is right, your options are to either look for a heuristic that will be always-efficient but not-always-optimal, or look for an always-optimal algorithm whose running time is not guaranteed to be always-efficient (e.g., by using a SAT solver).

Caveat: I don't have 100% confidence in my reasoning here.  If I understand things correctly, it seems to contradict another claim in the same paper (namely, the one mentioned below about adjacent transpositions; those generate a transitive group, yet the corresponding problem isn't NP-hard).  So I don't have full confidence that the problem is NP-hard.  It's entirely possible I've misunderstood something or mis-applied the paper's results.

Other resources

Subsequent work has also shown that certain special cases can be solved in polynomial time, e.g., where $T$ contains all transpositions, or where $T$ contains all adjacent transpositions $(i,i+1)$, or where $T$ contains all cyclicly adjacent transpositions (i.e., all transpositions of the form $(i,i+1)$ together with $(n,1)$).  However, that's probably not useful to you, as those correspond to rather trivial graphs (the complete graph, a line graph, or a $n$-cycle $C_n$).

You might also be interested in https://cstheory.stackexchange.com/q/21899/5038


Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms.  Given a directed graph $G=(V,E)$, an irreducible kernel is a graph $G'=(V,E')$ where $E'$ is a subset of $E$, and both $G$ and $G'$ have the same reachability (i.e. their transitive closures are the same), and removing any edge from $E'$ would not satisfy this condition, i.e. $E'$ is minimal (although not necessarily the minimum size possible).

A minimum equivalent graph is similar, except it also has the fewest number of edges among all such graphs.  Both of these concepts are similar to a transitive reduction, but not the same because a transitive reduction is allowed to have edges that are not in $E$.  That said, [1] proves that for every DAG, it has a unique irreducible kernel, which is also its unique minimum equivalent graph and its unique transitive reduction, and thus there is no benefit in the transitive reduction to using edges not in the original graph (there is a difference between minimum equivalent graph and transitive reduction for some graphs with cycles, but not for DAGs).

HTCS says that there is an algorithm to calculate an irreducible kernel of a directed acyclic graph in $O(V*e)$ time, where $V$ is the number of vertices, and $e$ is the number of edges in the irreducible kernel, i.e. the output of the algorithm.  The reference given for this is the following paper, which I have not been able to find an on line source for yet (links or other sources welcome -- I can ask at a research library soon if nothing turns up).

Noltemeier, H., "Reduction of directed graphs to irreducible kernels", Discussion paper 7505, Lehrstuhl f. Mathematische Verfahrensforschung u. Datenverarbeitung (Operations Research & Data Processing), Univ. Göttingen, Gottingen, 1975.

Does anyone know what this algorithm is?  It surprises me a little that it includes the number of edges in the output graph, since that would mean it should run in $O(n^2)$ time given an input graph with $O(n^2)$ edges that represents a total order, e.g. all nodes are assigned integers from 1 up to $n$, and there is an edge from node $i$ to $j$ if $i < j$.  That doesn't seem impossible, mind you, simply surprising.

[1] Aho, Garey, and Ullman, "The Transitive Reduction of a Directed Graph", 1972 https://epubs.siam.org/doi/10.1137/0201008

I do not know about their algorithm, but the problem is easy to solve in $\mathcal{O}(V \cdot e)$ time. The idea is to just do a DFS from every node to find vertices that can reach it. Normally this takes $\mathcal{O}(E)$ time, but we can use the irreducible kernel we have already built to do it in $\mathcal{O}(e)$ time.

First note that $e \geq n-1$ if the graph is connected. If it is not, solve the connected components individually.

Start by doing topological sort on the vertices, with vertices with indegree zero first. Loop vertices first-to-last. When at vertex $i$, first mark all vertices as unreachable. Then loop vertices from $i-1$ to $1$. At every vertex $j$, if $j$ is unreachable and has an edge to $i$ in the input graph, add the edge $(j, i)$ to the irreducible kernel and mark $j$ reachable. Then if $j$ is reachable, loop all edges $(t, j)$ in our kernel, and mark $t$ reachable.

The topological sort takes $\mathcal{O}(V + E)$ time, and the DFS takes $\mathcal{O}(E + V \cdot e)$ time, so since $e = \mathcal{\Omega}(V)$, the running time is $\mathcal{O}(V \cdot e)$.

The produced DAG has the same reachability as the original graph, as we use a subset of the original edges, and only skip adding the edge $(j, i)$ if $i$ is reachable from $j$ even without it.

Assume some edge $(j, i)$ can be deleted while maintaining reachability. But by the way we did the DFS, $i$ was not reachable from $j$ without the edge (note that any path between them can only visit vertices between them in the topological order). Hence the produced DAG is indeed irreducible.


Adding a vertex in graph in adjacent matrix repersentation In website geeksforgeeks i read that adding a vertex to graph in adjacent matrix takes O(V^2) time but i am not getting it. It requires adding a row and a column which should take linear time ?
I am a beginner hence forgive me for such a question

Link:- https://www.geeksforgeeks.org/graph-and-its-representations/

It more or less depends on the implementation. If you have implemented the matrix using linked lists (which isn't what we usually do), then adding a new vertex in $G$ will be linear in the number of vertices of $G$. But we don't usually use linked lists because then reading/checking an edge will take $V(G)^2$ time.

To allow random/constant time access of the adjacency matrix, we need to use fixed-size arrays of arrays (or matrix). Now, when you add new vertex, we are required to copy the whole matrix into a bigger size matrix: hence the quadratic time.

Generally, we use $vectors$ instead of $arrays$ which hold extra hidden memory, and hence it will indeed be linear time to add a vertex on average. https://www.geeksforgeeks.org/vector-in-cpp-stl/


Does space complexity analysis usually include output space? Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this out just by reading examples.

If a function returns a new list, should the space complexity analysis of the function include the space required for the output? There seem to be clear reasons to want to exclude the input from the analysis, but it's less clear if the output should be excluded. Does the architecture of the system matter (e.g. multi-tape turing machine vs modern RAM-based computer)?

Consider the example functions below. They all use O(1) auxiliary space but different output space (relative to the input space), so the overall space complexity changes based on whether or not you include the output space.

generate a new list from a single int input:

int[] random1(int count) {
    Random rand = new Random();
    int[] output = new int[count];
    for (int i = 0; i < count; i++) {
        output[i] = rand.Next();
    }
    return output;
}

Output space: O(2^n)

generate a new list from a list input:

int[] random2(int[] input) {
    Random rand = new Random();
    int[] output = new int[input.Length];
    for (int i = 0; i < input.Length; i++) {
        output[i] = input[i] + rand.Next();
    }
    return output;
}

Size of output: O(n)

modify the input list in place

int[] random3(int[] input) {
    Random rand = new Random();
    for (int i = 0; i < input.Length; i++) {
        input[i] = input[i] + rand.Next();
    }
    return input;
}

Size of output: O(1)

Typically, we consider space complexity in terms of Turing machines with:

one read-only input tape
one write-only output tape
however many read-write working tapes you want.

The space usage is the number of cells used on the working tapes, so input and output space typically aren't counted.  (See, e.g., Section 2.5 of Papadimitriou.)

Obviously, we don't want to count input space since, then, every algorithm would have to use linear space.  Likewise, we don't want to count output space as that stops us from distinguishing between problems that are hard simply because the output is big (e.g., given an integer $n$, write the list $1, 2, \dots, n$) and problems that are hard because even computing a single output is hard (e.g., output a list of all $3$-colourings of the input graph).

On the other hand, not all authors do this. Sipser defines space usage as just the number of tape cells read by an ordinary Turing machine (Section 8) and the says, more or less, "Oops but that doesn't let us consider any kind of sublinear space, so we'd better redefine it not to include the input" (Section 8.4; he's only considering decision problems, so there's no output to worry about).

I'm not a fan of the redefinition approach but, either way, we need to exclude the input and output if we want to talk about any kind of sublinear space bound.

References
C.H. Papadimitriou, Computational Complexity. Addison–Wesley, 1992.
M.  Sipser, Introduction to the Theory of Computation (3rd edition). Cengage Learning, 2013.


Does $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ imply anything? The assumption $\mathrm{SUBEXP}\subset \mathrm{P}/\mathrm{poly}$ seems to yield nothing interesting at all. Is that true?

Yes, we have to admit so. For other normal complexity class $\mathcal{C}$,

either $\mathcal{C}\subseteq \mathrm{PSPACE}$ then we have an interactive protocol with the prover to be replaced by the circuit,

or $\mathcal{C} = \mathrm{EXP}$ in this case, we utilize Meyer's to put $\mathcal{C}$ in $\Sigma_2^p\cap \Pi_2^p \subseteq \mathrm{PSPACE}$ to get back to the previous case.

But in the case of $\mathrm{SUBEXP}$, nothing above applies.

Note that in Meyer's, we have to simulate the machine deciding $\mathrm{L}\in \mathcal{C}$. But as every particular machine $\mathrm{M}$ deciding $\mathrm{L}$ runs in exponential time ($\mathrm{L}$ has infinitely many machines with ever decreasing running time bounds), we cannot have a multi-output circuit for it.