Why are some programming languages "faster" or "slower" than others? I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I have a few question regarding this:

Why does this happen?
What governs the "speed" of a programming language?
Has this anything to do with memory management?

I'd really appreciate if someone broke this down for me.

In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few.

Every language ultimately has to be run by executing machine code. A "compiled" language such as C++ is parsed, decoded, and translated to machine code only once, at compile-time. An "interpreted" language, if implemented in a direct way, is decoded at runtime, at every step, every time. That is, every time we run a statement, the intepreter has to check whether that is an if-then-else, or an assignment, etc. and act accordingly. This means that if we loop 100 times, we decode the same code 100 times, wasting time. Fortunately, interpreters often optimize this through e.g. a just-in-time compiling system. (More correctly, there's no such a thing as a "compiled" or "interpreted" language -- it is a property of the implementation, not of the language. Still, each language often has one widespread implementation, only.)

Different compilers/interpreters perform different optimizations.

If the language has automatic memory management, its implementation has to perform garbage collection. This has a runtime cost, but relieves the programmer from an error-prone task.

A language might be closer to the machine, allowing the expert programmer to micro-optimize everything and squeeze more performance out of the CPU. However, it is arguable if this is actually beneficial in practice, since most programmers do not really micro-optimize, and often a good higher level language can be optimized by the compiler better than what the average programmer would do.
(However, sometimes being farther from the machine might have its benefits too! For instance, Haskell is extremely high level, but thanks to its design choices is able to feature very lightweight green threads.)

Static type checking can also help in optimization. In a dynamically typed, interpreted language, every time one computes x - y, the interpreter often has to check whether both x,y are numbers and (e.g.) raise an exception otherwise. This check can be skipped if types were already checked at compile time.

Some languages always report runtime errors in a sane way. If you write a[100] in Java where a has only 20 elements, you get a runtime exception. In C, that would cause undefined behavior, meaning that the program might crash, overwrite some random data in memory, or even perform absolutely anything else (the ISO C standard poses no limits whatsoever). This requires a runtime check, but provides a much nicer semantics to the programmer.

However, keep in mind that, when evaluating a language, performance is not everything. Don't be obsessed about it. It is a common trap to try to micro-optimize everything, and yet fail to spot that an inefficient algorithm/data structure is being used. Knuth once said "premature optimization is the root of all evil".

Don't underestimate how hard it is to write a program right. Often, it can be better to choose a "slower" language which has a more human-friendly semantics. Further, if there are some specific performance critical parts, those can always be implemented in another language. Just as a reference, in the 2016 ICFP programming contest, these were the languages used by the winners:

1   700327  Unagi                       Java,C++,C#,PHP,Haskell
2   268752  天羽々斬                     C++, Ruby, Python, Haskell, Java, JavaScript
3   243456  Cult of the Bound Variable  C++, Standard ML, Python

None of them used a single language.

Your question is too general, so I'm afraid I can't give an exact answer that you need.

For my best explanation, let's look at C++ and .Net platform.

C++, very close to machine code and one of the favor programming in the older time (like more than 10+ years ago?) because of the performance. There isn't much resources needed to develop and execute C++ program even with the IDE, they are consider very light weight and very fast. You can also write C++ code in console and develop a game from there. In terms of memory and resources, I forgotten roughly how much capacity it takes in a computer but the capacity is something that you can't compare with current generation of programming language.

Now let's look at .Net. The prerequisite to do .Net development is one giant IDE that consists of not just one type of programming languages. Even if you just want to developer in let's say C#, the IDE itself will includes many programming platforms by default such as J#, VB, mobile and etc by default. Unless you do custom install and only install exactly what you want, provided that you are experience enough to play with the IDE installation.

Other than installing the IDE software itself, .Net also comes with huge capacity of libraries and frameworks for the purpose of ease of access to any kind of platform that developers need AND don't need.

Developing in .Net can be a fun experience because many common function and components are available by default. You can drag-and-drop and use many validation method, file reading, database access and much more in the IDE.

As a result, it's a trade off between computer resources and speed of development. Those libraries and framework takes up memory and resources. When you execute a program in .Net IDE, it may consume tons of time trying to compile the libraries, components and all of your files. And when you do debugging, your computer require lots of resources to manage the debugging process in your IDE.

Usually, in order to do .Net development, you need a good computer with the some Ram and processor. Otherwise, you might as well don't programming at all. In this aspect, C++ platform is much better than .Net. Although you still need a good computer, but capacity won't be too much of concern compare to .Net.

Hope my answer could help with your question. Let me know in case you want to know more.

EDIT:

Just a clarification to the my main point, I mainly answer to the question of "What's govern the speed of programming".

In IDE standpoint, using C++ or .Net language in the relative IDE does not affect the speed of writing the code, but it will affect the speed of development because Visual Studio compiler take longer time to execute the program, but C++ IDE is much lighter and consume less computer resources. So in the long run, you can do programming faster with C++ type of IDE compare with .Net IDE which heavily depending on libraries and framework. If you take in the amount of time of waiting the IDE to start up, compile, execute the program and etc, it will affect the speed of programming. Unless "the speed of programming" is actually only focus on "speed of writing code".

The amount of libraries and framework in Visual Studio also consume the computer capacity. I'm not sure if this answer the question of "memory management", but I just want to point out that Visual Studio IDE can take up lots of resources when running it, and thus slow down the overall "speed of programming". Of course, this has nothing to do with "speed of writing code".

As you may have guessed, I don't know too much of C++ as I just use it as example, my main point is about Visual Studio type of heavy IDE that consume computer resources.

If I got the idea and did not answer the thread starter question at all, apologize for the long post. But I would advice the thread starter to make the question clear and ask exactly what he/she need to know about "faster" and "slower"


Solving $T(n) = 4T(n/2) + n^2log_2(n)$ My first thought was using the third case of the master theorem, but I am not sure if I can use $\epsilon \rightarrow 0$, so $f(n) \in \Omega(n^{log_2^4+\epsilon})$.

Otherwise, I tried solving the equation by iteration where I got $T(n) \in \Theta(n^2log_2^3n)$ instead of $T(n) \in \Theta(n^2log_2n)$.

Which solution is right and why? Thanks.

When you applied the master theorem, f(n) is n^2 right. This is anyways asymptotically lesser than O(n) which is the n^2log(n). Hence at each node of the recursion tree, the O(n) would dominate computation hence T(n) is O(n). The reason why this is true is because when you apply the recursion tree the number of processes at each node if you calculate would be 2O(n/2)+4O(n/4)...... whose sum turns out to be lesser than O(n).


Worst case analysis of $100n + 5$ for different $n$ For the function $f(n) = 100n + 5$, what is the asymptotic complexity of $f(n)$ in terms of Big O notation. I guess it is $O(n)$, but how can I prove it ?

Big-$O$ is the set of functions
$$O(f)=\{g\colon \exists C>0, \exists N \in \mathbb{N}, \forall n > N, g(n) \leqslant Cf(n)  \}$$
So we can write $100n+5 \leqslant  105\cdot n$, taking $C=105, N=1$, and we obtain
$$100n+5 \in O(n)$$

All you need is to write the definition of Big O notion:

f(n) = O(n) if and only if there is a c and an m such that for all n :
100n+5 > cn for all n > m

If you can find such m and c then you have proven f(n) = O(n). c and m can be 10 and 11 (as an example).


Design a CFG that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b } I am trying to design a context-free grammar that generates the language { x in {a,b}* | the length of x is odd and its middle symbol is a b }.

This is really confusing me, I'm having trouble with making sure that b is always in the middle. Any help?

PDA:

Here is a guideline to solve this problem:

Try to think how to "count the letters until the middle", then "guess" where the middle is, and then "verify that your guess was really the middle, by counting once again"

CFG:

$S\rightarrow b\space | \space xSy$ for every $x,y\in \{a,b\}$

Yea, thats everything in the CFG!


Fastest known algorithm for $3$-$\mathrm{Partition}$ problem $3$-$\mathrm{Partition}$ problem is $\mathsf{NP}$-Complete in a strong sense meaning there is no pseudo-polynomial time algorithm for it unless $\mathsf{P=NP}$. I am looking for the fastest known exact algorithm that solves $3$-$\mathrm{Partition}$.

Is there a fast (e.g subexponential) algorithm for $3$-$\mathrm{Partition}$? Is it possible to solve it faster than using SAT solvers?

If you find a fast (sub-exponential) exact algorithm for 3-Partition , while 3-Partition is NP-Complete, then dear sir you have just proven P=NP, which no body has done so far, and you have a 1M $ price waiting for you as well as wealth and fame, cheers.

Anyway if you do have a faster than a SAT solver, wouldn't you actually be performing SAT it's self faster? I mean if you can reduce SAT to 3-PARTITION and you can solve 3-PARTITION in sub-expo time, doesn't that mean that SAT can be solved in sub-expo time, hence all NP-COMPLETE problems also can be solved in such time? So you might as well be looking for a sub-expo time solution of any other NP-COMPLETE problem just as well, it would still be a significant breakthrough.


Finding paths from the result of max flow Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them.
I would like to enumerate all possible sets of paths that comprise the maxflow.
That is, each set of paths will make the max flow.
But I suspect there could be multiple set of such paths.

Give the edges some value of priority. Once you have run a given maxflox algorithm, reduce the priority of a given edge by the amount of flow which got through the last time. This way edges which have gotten flow through them the last time running the algorithm will not be chosen as the first flow first this time and another way, if any, will be produced.


Is L={0,1}* without strings that start with 00 decidable? Say you have a language L = "{0,1}* without strings that start with 00". How do you prove this is decidable?  I'm drawing a blank on this one.

so turns out its decidable because its the regular expression $L = 01(0|1)$*


Exercise on Divide&Conquer's technique I need help on this exercise:
You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(n log n).

I find a solution but in O(n^2)... How can I apply D&C?

Given an array of elements $a[i], 0\le i\le n-1$, we know we can sort it in time $O(n\log n)$. Then do the following to produce an array $b[\;]$:

declare b to be of size n
old = a[0]
b[0] = a[0]
j = 1
for i = 1, ... , n
   if a[i] =/= old    // found a new value
      old = a[i]      // save it
      b[j] = a[i]     // store it in b[j]
      j = j + 1       // and increment the b index

It's clear that, first, this can be done in one pass through the $a$ array, so this part will take time $O(n)$ (along with $O(n)$ time to allocate $b$), and, second, after this part the $b$ array will contain all of the values of the original array, with no duplicate values.

Note. This may or may not be what you want. Starting with an initial array $\langle\,7, 3, 7, 4, 1, 3, 1, 7\,\rangle$, this will result in a $b$ array $\langle\,1, 3, 4, 7\,\rangle$, which has all the values without duplicates, but the original place order of the elements isn't preserved. There are at least two possibilities for the result, depending on whether you want to eliminate all the duplicate values after the first occurrence, (giving you $\langle\,7, 3, 4, 1\,\rangle$) or if you want to eliminate all the duplicate values before the last occurrence, giving you $\langle\,4, 3, 1, 7\,\rangle$.

For the first option, a fairly simple modification is to do a preprocessing step on the $a$ array, changing it to an array of pairs, $(value, index)$, where $index$ is the position of the element with that value. In the example above, this will give you a new array
$$
\langle\,(7, 0), (3, 1), (7, 2), (4, 3), (1, 4), (3, 5), (1, 6), (7, 7)\,\rangle
$$
Now, as we did originally, sort this array by the first element of the pairs, giving
$$
\langle\,(1, 4), (1, 6), (3, 1), (3, 5), (4, 3), (7, 0), (7, 2), (7, 7)\,\rangle
$$
(here we need to use a stable sort, like mergesort, to maintain the original place order). Eliminating duplicates, as above, we will have
$$
\langle\,(1, 4), (3, 1), (4, 3), (7, 0)\,\rangle
$$
and if we sort the result by the second index, we'll have
$$
\langle\,(7, 0), (3, 1), (4, 3), (1, 4)\,\rangle
$$
and looking at the first element, we'll have $\langle\,7, 3, 4, 1\,\rangle$, which is what we wanted.

This algorithm will take $O(n)$ steps to preprocess the array, $O(n\log n)$ steps to sort the result, $O(n)$ steps to eliminate the duplicate values, and $O(n\log n)$ steps to do the final sort, giving us an algorithnm that runs in time $O(n+n\log n+n+n\log n)=O(n\log n)$.

This is my solution (pseudocode):

Duplicate(A: array):
  Array B = Merge-sort(A)
  Array Vect // New Vector
  int p=2
  Vect[1] = B[1]
  for i=2 to B.lenght{
    if (B[i]<>B[i-1]) then
        Vect[p] = B[i]
        p = p+1
   }
 return Vect

is correct?


Why polynomial time is called "efficient"? Why in computer science any complexity which is at most polynomial is considered efficient?

For any practical application(a), algorithms with complexity $n^{\log n}$ are way faster than algorithms that run in time, say, $n^{80}$, but the first is considered inefficient while the latter is efficient. Where's the logic?!

(a) Assume, for instance, the number of atoms in the universe is approximately $10^{80}$.

Another perspective on "efficiency" is that polynomial time allows us to define a notion of "efficiency" that doesn't depend on machine models. Specifically, there's a variant of the Church-Turing thesis called the "effective Church-Turing Thesis" that says that any problem that runs in polynomial time on on kind of machine model will also run in polynomial time on another equally powerful machine model.

This is a weaker statement to the general C-T thesis, and is 'sort of' violated by both randomized algorithms and quantum algorithms, but has not been violated in the sense of being able to solve an NP-hard problem in poly-time by changing the machine model.

This is ultimately the reason why polynomial time is a popular notion in theoryCS. However, most people realize that this does not reflect "practical efficiency". For more on this, Dick Lipton's post on 'galactic algorithms' is a great read.

Polynomial time algorithms are considered efficient only in comparison with the hardest non-polynomial time  especially the so called NP-Complete.
See image: Euler diagram for P, NP, NP-complete, and NP-hard set of problems.


Recover permutation from prefix sums, using segment trees? I encountered the following problem on Codeforces.

  An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $[3,1,2],[1],[1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2],[1,1],[2,3,4]$.

  There is a hidden permutation of length $n$.

  For each index $i$, you are given $s_i$, which equals to the sum of all $p_j$ such that $j<i$ and $p_j<p_i$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.

  Your task is to restore the permutation.

How can I solve this problem using segment trees in $O(n\log n)$ time?

I tried to understand the solution on Codeforces but I could not understand it.  Their solution:

  Let us fill the array with numbers from 1 to $N$ in increasing order.

  1 will lie at the last index $i$ such that $s_i=0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_i$ values by $1$. Repeat this process for numbers $2,3,\ldots,N$. In the $i$th turn, reduce the elements by $i$.

  To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.

I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $O(\log n)$ time in this case.  Can you show me an example input and show me what happens in each iteration?

My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.

For example: Suppose I have sample input:

5
0 1 1 1 10

My segment tree will look like:

                           [1-5](0)
                          /        \
                      [1-2](0)      [3-5](1)
                    /      \         /      \
                [1-1](1) [2-2](1)   [3-4](1) [5-5](10)
                                   /       \
                              [3-3](1)      [4-4](1)

Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $O(n)$ time.

The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the sums $s_i$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop.

Since the sequence of minimum positions was P = [1, 4, 3, 2, 5], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is [1, 4, 3, 2, 5], the inverse of P (although in this case it's the same).


Can a quantum computer (theoretically) do things a classical computer (literally) can't? I've been searching the net for an answer to this question, but it's guetting quite confusing.
I want to know if there are some undecidable problems for a classical computer that a quantum computer could do.
The examples I've seen are things like Shor's algorithm, but that's "just" because the quantum computer is more powerfull than the classical one, and can do stuff like Integer factorization faster. Or at least that's how I understand it so far.
Basically my question is this : is there anything a quantum computer can do that a regular one can't if said regular computer had infinite power (or processing speed or whatever)?
Examples, explanations, sources would be greatly appreciated, but a simple yes/no would please me also.

No. Quantum computers cannot solve undecidable problems.

A quantum computer can be simulated by a classical computer. So, if a quantum algorithm could solve an undecidable problem, then we could also solve it classically via simulation.  However, we already know that if a problem has no classical solution, then it must not have a quantum solution either.

Also, you said:

  that's "just" because the quantum computer is more powerful than the classical one.

This is an open problem.  We do not yet know if $BPP \subset BQP$.

I quantum computer isn't more powerful than a classical one, according to Church-Turing's thesis, a function on the natural numbers is computable if and only if it is computable by a Turing machine, that means that there isn't a computer model that is more powerful than a Turing Machine.


What is the theoretical result of flattening a list containing only itself? Consider the following python code
X = [None]
X[0] = X

This has many fun properties such as
X[0] == X

and
X[0][0][0][0][0][0][0][0] == X

I understand how this works from a practical standpoint, as it's all just the same pointer.
Now, when flattening a list, we tend to convert things from
[[1, 2, 3], [[4, 5], [6, 7]], 8, 9]

to
[1, 2, 3, 4, 5, 6, 7, 8, 9]

In this case, I am considering flattening to be reducing a multi-dimensional list down to a single list of only non-list elements.
In practice, flattening this list would be impossible, as it would create an infinite loop.
This may be more mathematical in nature, but I'm unsure how to put it in mathematical terms. Suppose we could flatten this list, would the result simply be the empty list?
For context, I initially got this idea by considering the list
X = [[], []]
X[0] = X

It is clear to see that at each pass of flattening, the empty list that is the second element simply disappears. This lead me to think that the overall result, may be the empty list.
Could it be possible that flattening this list would theoretically produce an infinitely long list of the list itself, as in
X == [X, X, X, X, X, X, ..., X]

This is purely a fun thought exercise. Any insight and discussion on this would be appreciated.
P.S. Although I'm looking for an answer in plain terms, if anyone is more mathematically inclined, I would be interested to see how this problem could be formulated in some sort of set notation. Please feel free to point me to a relevant math exchange thread as well.
P.P.S. I would also be interested in a solid proof (not formal) to go along with the answer.

From a mathematical point of view, this is impossible: there is no such a thing as a set containing itself (in normal logic sense) or a vector who has itself as an element, so this question doesn't really mean anything outside the realm of using pointers in a list
BUT, on a second thought: I might be able to formulate what "flattening" is if you allow me to define things however I want.
Lets say our world is some graph $G$, nodes in it would be elements, and an edge $(v,u)$ would mean that the element $v$ contains the pointer to $u$. Then, in those terms, the array [[5,6],3,[7]] might look like this:

Flattening the graph in this sense means to take every non-direct child of the root node (the array's node) and make it a direct child of it.
Then, your array X looks like this:

And when you flatten it you would remain with the exact same graph, and therefore in this sense when you flatten X you would get simply X itself.
However, this is truly meaningless because it's only by the definition I just made up: you could have defined it in another way and it would have resulted in something else maybe!


minimum subset of dominating 2D points From an initial set $S$ of 2D points, how to efficiently compute a minimum(-size) dominating subset $M$ ?

$M$ is a dominating subset of $S$ if for any $(x,y)$ in $S$ there is at least one point (a,b) in M such that $x \le a$ and $y \le b$

Another related question: is any minimal set also minimum?

It is trivial to find a minimal set in $|S|^2$ time complexity.

$O(N^2)$ solution

First of all define dominant relation for points:

  Point $d(x_d, y_d)$ is dominating point $p(x_p, y_p)$ iff $x_p \le x_d$ and $y_p \le y_d$. Also easy to see that this relation is transitive, i.e. if $a$ dominating $b$ and $b$ dominating $c$, then $a$ dominating $c$.

Let $M$ be minimum(-size) dominating subset of set $S$. Now we need to check which point will be in $M$. Let answer on the question:

  Is $p \in S$ is $M$ or not?

We have 2 cases:

$\nexists d \in S, d$ is dominanting $p$, then $p \in M$, if we will not include $p$ in $M$ we will not be able to find a point that will dominate $p$.
$\exists d \in S, d$ is dominanting $p$, then $p \notin M$, because it will be more optimal include $d$ in $M$ and exclude $p$, as every point in $A$ that is dominated by $p$ is dominated by $d$ also, but $d$ is dominating at least one more point (itself).

First case make sure that $M$ will dominate $S$, second case that $M$ is minimal among all dominating subsets.

And now we have easy $O(N^2)$ solution: for each point $p \in S$ check membership in $M$; to do that we need to check that there is no point $d \in S$ that dominating $p$.

$O(N \log N)$ solution

To construct solution with $O(N \log N)$ time-complexity, let see some example of sets $S = \{A, B, C,..., N\}$ and $M = \{N, B, I, H\}$:

To find $M$ we need to sort points in $S$ by $x$ in descending order, and if $x's$ the same by $y$ in descending order (it can be done in $O(N \log N)$, let call this sorted list $L$.

Include first point from $L$ in $M$ and remember this point as $T$.
Iterates through $L$ (let $C$ current considered point from $L$):

if $C$ is dominated by $T$ than skip $C$ and go to next point in $L$;
else include $C$ in $M$ and set $T = C$
This step can be performed in $O(N)$.

I have built a new algorithm to find the minimal set M but I can't check whether the algorithm is correct or not. The algorithm is as follows:
1. Consider the new array formed by multiplying the abssica array and
     the corresponding ordinate array and arrange it in ascending order.
     Next we arrange the abssica array and the ordinate array
    according  to the new array formed.
2. Next we define the quantity:(diff of abssica)*(diff of ordinate)=m.
     We initialize m=0 and also min=m.
3. Next we include the last elements of the new abssica  and
    ordinate array formed by the arranging the original ones in M.
4. Now we check m for  the second last point of the new abssica
    and ordinate array and if mmin we leave this point and check the third
    last point and this goes on till the new abssica and ordinate arrays
    get  exhausted.
Just tell me about the correctness of the algorithm. There is no need to worry about time complexity. Its O(nlgn).


Cost of shifting a number I was wondering what would be a time complexity of shifting a binary or a decimal number?
For example: 0011, when I shift it left I get 0001.

I was thinking that the time complexity is $\Theta(n)$, because we have to shift every number.

I need it to calculate $m*{b^\frac{n}{2}}$, where $m$ is some number
and $b$ might be 2 (in case of binary) or 10 (decimal).
Therefore instead of multiplication, I just shift to multiply, and therefore complexity is $\Theta(n)$.

Am I correct or is my thinking wrong?

Time complexity is not god-given but is rather defined by the model of computation. To take a simple example, what is the time complexity needed for adding two numbers? In the RAM machine model, this operations takes constant time, as long as the numbers are not "too big". The rationale is that modern hardware implements addition as a fast machine instruction; if the numbers are not "too big" then they fit into single registers. The same reasoning holds for shifts. You have to be careful, however, that the size of the relevant quantities doesn't blow up.

O(n) and CPU execute in one Register then put the result to another Register, so the performance is quick.

Reference
http://chortle.ccsu.edu/assemblytutorial/Chapter-12/ass12_2.html


Time complexity of $T(n) = nT(n-1) + n^2$ This time complexity comes from $N$-queen problem. There are many threads talking about the time complexity to be $O(n!)$ but I cannot figure out how we get it. Here is the progress I have so far:

$$
\begin{align}
T(n) & = n T(n-1) + n^2\\
& = n(n-1)T(n-2) + n(n-1)^2 + n^2\\
& \vdots\\
& = n! + n! + n(n-1) \dots 2^2 + n(n-1) \dots 4*3^2 + \dots + n(n-1)^2 + n^2
\end{align}
$$

RHS and LHS divided by $n!$

$$
    \frac{T(n)}{n!} = 2 + \frac{2}{1!} + \frac{3}{2!} + \dots + \frac{n-2}{(n-3)!} + \frac{n-1}{(n-2)!} + \frac{n}{(n-1)!}
$$

From comments in GeeksForGeeks the RHS converges to a constant. Can anyone please explain why the RHS converges to a constant?

We can compute the limit explicitly:
$$
1 + \sum_{n=0}^\infty \frac{n+1}{n!} = 1 + \sum_{n=0}^\infty \frac{1}{n!} + \sum_{n=1}^\infty \frac{1}{(n-1)!} = 2e + 1.
$$

(skip to Part II)

You might find it easier to think about it this way.

First think of the definition of $n!$

$n! = n(n-1)!$

where $1! = 1$

The ! "operator" is just a notation convenience, it might as well have been written as $R(n)$

$R(n) = nR(n-1)$

where $R(1) = 1$

The idea so far is that $n! = R(n)$

Then think of the definition of $T(n)$ and how it relates to $R(n)$ (or $n!$)

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

$T(n) > nR(n-1) + n^2 = n! + n^2$

$T(n)$ is greater than $R(n)$ because of the $n^2$ term on every iteration. With this you have already proved that $T(n)$ is at least $O(n!)$

This doesn't proof $T(n)$ is $O(n!)$ as you might need a bigger function.

Part II

By the definition of big-O we're now interested in proving there exists constants $c$ and $k$ such that $T(n) \leq cn!$ for $n \geq k$.

$T(n)/n! \leq c$

expanding $T(n)$ you'll find

$T(n)/n! = (nT(n-1) + n^2)/n! = nT_{n-1} / n! + n^2/n! = T_{n-1}/(n-1)! + n^2/n!$

You can expand that a couple more times to realise
$T_n/n! = T_{n-k}/(n-k)! + \sum_{i=0}^{k-1}{(n-i)^2/(n-i)!}$

With $k = n - 1$ and defining $T_1 = 1$ as the base case:

$T_n/n! = 1 + \sum_{i=0}^{n-2} {(n-1)^2/(n-1)!}$

The summation term converges (in each "iteration" it grows less and less), that guarantees that if we find a $c$ for a given $k$, then it will also work for all $n \geq k$. To find $c$, just substitute $n$ on the above equation for any value you'd like $k$ to have.


Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers I want an algorithm to list all possible ways to map a series of integers $M = \{1,2,3,...,m\}$ to another series of integers $N = \{1,2,3,...,n\}$ where $m > n$, subject to the constraint that only contiguous integers in $M$ map to the same integer in $N$.

E.g.: 5 -> 2:
  (1, 2, 3, 4), (5)
  (1), (2, 3, 4, 5)
  (1, 2, 3), (4, 5)
  (1, 2), (3, 4, 5)

This seems like it should be a standard problem with a well known solution, but I can't find it.

To clarify, I am not looking for the total number of solutions, but for pseudocode or the name of a corresponding algorithm to exhaustively list all solutions.

Suppose that the image of your mapping has size $k$. This implies a division of $\{1,\ldots,M\}$ into $k$ contiguous intervals. By identifying each such interval with its largest point, we see that there are $\binom{M-1}{k-1}$ such partitions (since $M$ is always one of the $k$ largest points). For the actual colors chosen, the number of choices is $N(N-1)\cdots(N-k+1) = N!/(N-k)!$. The total number of mappings is thus
$$
 \sum_{k=1}^N \frac{N!}{(N-k)!} \binom{M-1}{k-1}.
$$
Using this argument, it is not too hard to construct an algorithm to list all such mappings; the algorithm completely mirrors the argument.

Attempted a solution in python (start corresponds to the first element in $M$, stop-1 corresponds to the last element in $M$, and nbins corresponds to $|N|$):

import itertools
def find_bins(start, stop, nbins):
    if (nbins > 1):
        return list(list(itertools.product([range(start, ii)], find_bins(ii, stop, nbins-1))) for ii in range(start+1, stop-nbins+2))
    else:
        return [range(start, stop)]

It gives a human readable answer, but the output needs some cleanup.


Online generation of uniform samples A source provides a stream of items $x_1, x_2,\dots$ . At each step $n$ we want to save a random sample $S_n \subseteq \{ (x_i, i)|1 \le i \le n\}$ of size $k$, i.e. $S_n$ should be a uniformly chosen sample from all $\tbinom{n}{k}$ possible samples consisting of seen items. So at each step $n \ge k$ we must decide whether to add the next item to $S$ or not. If so we must also decide which of the current items to remove from $S$ .

State an algorithm for the problem. Prove its correctness.

Due to the dubious nature of the question, I only provide hints.

Have you tried the obvious? With probability $\frac{1}{n}$, add the new element to the sample. If it is added, choose one of the elements already in the sample uniformly at random and drop it. Sounds about fair, does it not?

For a proof, you will have to proceed inductively. In the step, you assume that $S_{n-1}$ is indeed a uniform sample. From this and the way you choose whether to include $x_n$ and which element to drop, you have to get that $S_n$ is a uniform sample, too.

Try if you can prove above idea correct. If it is not, find out where the problem is and fix it. See this answer to a similar question for a detailed application of this technique.

The best algorithm for your problem is Reservoir Sampling Algorithm. Read this


Sum of divisors summatory function with Erathosthenes' sieve I ran across the following problem from an online problem bank: there are up to $~10^5~$ queries each of which asks to compute the sum
$$\sum_{k = L}^{R} \sigma(k)$$
where $\sigma(k)$ is the sum of divisors of $k$. It is given that $1 \leq L \leq R \leq 5\cdot 10^6$.

My solution (described below) is based on Erathosthenes's sieve. I've implemented it in C++ and it works in about $0.9$ seconds on average which is too slow. I know that this problem can be solved at least twice faster but don't know how.

So here is my solution (arrays are 0-based):

M = 5 * 1e6
M = array of zeroes of size M + 1
A[1] = 1
for (k = 2; k <= M; k += 1)
    for (j = k; j <= M; j += k)
        A[j] += k

I precalculate $\sigma(k)$ via Erathosthenes' sieve for each $k$ below max possible value. When the main loop reaches $k$,  $A[k]$ keeps the value of $\sigma(k)$. Then I reassign $A[k]$ to be $\sum_{i=1}^{k}\sigma(i)$. After such preprocessing all queries can be computed in $O(1)$ time by computing $A[R] - A[L-1]$.

How can I make it faster? I know two formulas:
$$ (a) ~~~~~ \sigma(p_{1}^{a_1} \cdots p_{s}^{a_s}) = \prod_{i=1}^{s} \frac{p_{i}^{a_i + 1} - 1}{p_{i} - 1}$$
$$ (b) ~~~~~ \sum_{k=1}^{n} \sigma(k) = \sum_{k=1}^{n} k \left \lfloor \frac{n}{k} \right \rfloor$$

The problem with (a) is that computing it (at least in my implementation) is slower than given above. The problem with (b) is that I don't understand how to compute prefix sum with such approach faster than in $O(n^2)$ time.

Is there a more efficient algorithm for this problem?

(The problem bank credits the original source of the problem as 2012 Kharkiv, Winter School, Day of Sergey Kopelovich, Problem H.)

This isn't really computer science...

You create a table d where you store the sum of the divisors of k, for k = 1 to M, where M = $5 · 10^6$. That's the part that is time critical. Then you create a table s where you store the sum of divisors for all 1 ≤ j ≤ k, for k = 1 to M. That's easy, $s_0 = 0$, $s_{k+1} = s_k + d_{k+1}$. And then f (L, R) = $s_R - s_{L-1}$.

The first table is the problem. You handle this in $O (n \log n)$. And you only need a factor two, you say...

You will have an array d with 5 million entries, likely 4 byte per entry = 20 Megabyte. On a typical processor that you would have in your home computer, 20 Megabyte doesn't fit into any cache. And your code does lots of accesses to elements of that array in quasi random order. For each potential divisor k, you visit all numbers that are divisible by k, and increase the sum of divisors by k.

Let's do that with fewer visits: When you visit j which is divisible by k, add the two divisors k and j/k. But when you do that, start with $j = k^2$, adding only k (because k = j / k, and you don't want to count the divisor twice), and then add k and j / k for further j. You don't need to divide, because j / k will equal k+1, k+2, k+3 etc. We initialise the array for the case k = 1, that is setting A [j] = 1 + j / 1 for j ≥ 2.

A [1] = 1
for (j = 2; j ≤ M; j += 1)
    A [j] = 1 + j

for (k = 2; k*k ≤ M; k += 1)
    j = k*k
    A [j] += k
    j += k
    s = k + (k + 1)
    while j ≤ M
        A [j] += s
        j += k
        s += 1 // s equals k + j / k

You don't save operations. However, you are now accessing the array A in a much more regular pattern, so this will save you time because access to the items will be faster. j will be smaller, making the number of iterations for each j larger, which will make branch prediction work better.

For more improvement, you would find out how many array items fit into the processor cache in your computer, then perform the whole code for subranges of the array only (for example changing only A [0] to A [99999], then changing A [100000] to A [199999], and so on). That way, most memory accesses will only access cache memory, which might be substantially faster.

You are doing N lookups in a table of size M. If M is substantially larger than N, then you should probably think about approaches that don't build this table, and that may be a lot slower per lookup, but faster overall due to the small number of lookups. Even in the case here where N ≤ 100,000 and M = 5,000,000, you might for example not count divisors 1, 2, 3, 4, j/1, j/2, j/3, j/4 in the table (which makes it a bit faster to build), and handle that during the lookup.

Or you could add the sum of the divisors for odd numbers only, then calculate the sum of divisors for even numbers (if the sum of the divisors of an odd k is s, then the sum for 2k is 3s, for 4k it is 7s, for 8k it is 15s etc), which would save almost a factor 2.

PS. I measured it... making the algorithm for counting all sums of divisors more cache friendly by adding both j and k/j doubled the speed. Calculating the sum of divisors for odd k first, then calculating even k from the odd values, makes it a total of 7 times faster. Obviously all just constant factors.

You may store precalculated results for intervals  {L=1, R = k*10^4} and brute-force only about 2*10^4 numbers


How can I combine my interests for pure mathematics and computer science in college? I’m a high school senior who's gone through quite the self-introspection the past few months while applying for college, and I have a bit of a dilemma. All my life, I've loved & excelled at mathematics, and wants to study & explore it very much in depth in college. I get very excited when I read up on fields such as number theory, analysis, topology, and algebraic geometry. On top of that, I've also realized that although I have no experience programming, there are wonderful merits to applying math to computer science and would love to apply my math skills to a fast-growing industry.

I feel, however, that studying comp sci will "limit" the scope and depth of the math I study, because joint programs of math and comp sci will only make you take math classes relevant to the study of computer science. Out of the Common App colleges I'm applying to, Emory, NYU, and BU have joint majors in math and computer science, while UMiami only has a BS in mathematics, and Georgia Tech has BSs in discrete and applied mathematics. For Emory, for instance, I'll be "missing out" on multivariable calculus, complex variables, real analysis, and abstract algebra.

If there is a way to combine these two interests without limiting the mathematics I learn, that'd be amazing, but if not, so be it. If you feel I have certain misconceptions, please feel free to point them out. Lastly, I know this is not the best place to ask this question, as it is directed towards students and researchers of computer science, but I would love your input and appreciate it ahead of time!

Thank you!

Math is heavily used in both computer security, machine learning and AI.

Computer Security, such as encryption and related fields is all about finding math that makes it impossible to retrieve information without being the intended recipient.  With quantum computing possibility being a reality within the next 10 - 20 years there is a lot of work needed to come up with new ways of securing data.  Number theory is very relevant here.
Machine learning is heavily based on statistics.  new algo's with better capability of prediction is always relevant, and a very hot topic.
AI, while strictly an area of machine learning, are typically resolving to other areas of of learning than typical stats.  Any advancements in this areas will be done by people with strong math background.


Is it a problem to be a programmer with no knowledge about computational complexity? I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess.

Then I made the most trivial thing that came into my mind and then showed to my lecturer. After a brief observation, he perceived that the runtime complexity of my solution was inviable and shown something more efficient. And there is a tradition of programmers who have no idea on what is computational complexity (I was one of those), so is it a problem if a programmer has no idea on what is computational complexity?

Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but if you want to write a program that tackles serious problems you need it.

In your specific case, your example of finding connected components might have worked for graphs of up to say $100$ nodes. However, if you tried a graph with $100.000$ nodes then your lecturer's algorithm would probably have managed that in 1 second, while your algorithm would have (depending on how bad the complexity was) taken 1 hour, 1 day, or maybe even 1 eternity.

A somewhat common mistake students make in our algorithms course is to iterate over an array like this:

while array not empty
    examine first element of array
    remove first element from array

This might not be the most beautiful code but in a complicated program something like this might show up without the programmer being aware of it. Now, what is the problem with this program?

Suppose we run it on a data set of $100.000$ elements. Compared to the following program, the former program will run $50.000$ slower.

while array not empty
    examine last element of array
    remove last element from array

I hope you agree that having the knowledge to make your program run $50.000$ times faster is probably an important thing for a programmer. Understanding the difference between the two programs requires some basic knowledge about complexity theory and some knowledge about the particulars of the language you are programming in.

In my pseudocode language, "removing an element from an array" shifts all the elements to the right of the element being removed one position from the left. This makes removing the last element an $O(1)$ operation since in order to do that we only need to interact with 1 element. Removing the first element is $O(n)$ since in order to remove the first element we need to shift all the other $n-1$ elements one position to the left as well.

A very basic exercise in complexity is to prove that the first program will do $\frac{1}{2}n^2$ operations while the second program uses only $n$ operations. If you plug in $n=100.000$ you will see one program is drastically more efficient than the other.

This is just a toy example but it already requires a basic understanding of complexity to tell the difference between the two programs, and if you are actually trying to debug/optimize a more complicated program that has this mistake it takes an even greater understanding to find out where the bug is. Because a mistake like removing an element from an array in this fashion can be hidden very well by abstractions in the code.

Having a good understanding of complexity also helps when comparing two approaches to solve a problem. Suppose you had come up with two different approaches to solving the connected components problem on your own: in order to decide between them it would be very useful if you could (quickly) estimate their complexity and pick the better one.

If you don't know big-O you should learn it. It's not hard, and it's really useful. Start with searching and sorting.

I do notice that a lot of answers and comments recommend profiling, and they almost always mean use a profiling tool.

The trouble is, profiling tools are all over the map in terms of how effective they are for finding what you need to speed up.
Here I've listed and explained the misconceptions that profilers suffer from.

The result is that programs, if they are larger than an academic exercise, can contain sleeping giants, that even the best automatic profiler cannot expose.
This post shows a few examples of how performance problems can hide from profilers.

But they cannot hide from this technique.


Detecting coplanarity by given pairwise distances Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints.  Note that we're not given the coordinates of the points in V.  We may not even be given all pairwise distances, so the graph need not be complete, and it may even be sparse.

Suppose we're given $k$ and told that there are $k$ planes such that all the vertices belong to at least one of those plane. We want to find $k$ such planes, with an added restriction:

In order to determine whether 4 points are coplanar given only their pairwise distances, the most straightforward method is to use the Cayley-Menger determinant.  For our problem, this would require the graph to be fairly dense, since we'd need to know most of the pairwise distances to apply Cayley-Menger.  The restriction is to find $k$ planes without using the Cayley-Menger determinant.

If this is impossible, can we obtain a proof that states this is impossible?  In other words, can we prove that for any such graph $G$ and given $k$, if we have enough information to find $k$ planes for $G$ by some means, then we have enough information to use Cayley-Menger to find $k$ planes?

I think that if the input graph is 3-connected, and you assume some arbitrary origin and orientation, you can recreate the original points. Especially if you can find K_4 to seed the triangulation process.

Once we have the points, greedy strategies become available. They might not be optimal, but maybe they're enough for your purposes.

I've asked about recovering the embedding as a separate question.

Random Greedy

Until we have fewer than three not-disqualified points, arbitrarily pick three of them, yield the plane going through them, and mark all points on the plane as disqualified.

Take the remaining not-disqualified points (if any), pair them with some arbitrary disqualified points, and yield the plane going through them.

The planes we yielded covered all of the points. The number of planes we yielded is at most $\frac{n}{3}$, and each requires scanning through the remaining points, so this algorithm takes $O(n^2)$ time (faster than computing a determinant).

If the number of planes $k \ll n$, then we have reasonably good odds of hitting one of the large planes. I'm not sure what the expected running time is, but I would wild-guess it at $O(n \, k^3 \log k)$. (That's based on the coupon collector problem implying we need $\approx k \log k$ hits to collect $k$ planes, and that the odds of a hit are $\approx (1/k)^2$ so the expected time between hits is $\approx k^2$).

Prioritized Greedy

Another thing we can do, if we can solve for the points, is iterate over all triplets and count how many points are on that plane. Then we repeatedly yield the plane covering the most points, until no points are left.

If we don't account for disqualified points when choosing the next plane, then this takes $O(n^3 \log t)$ time where $t$ is the number of planes we return. If we do re-prioritize, then I think it can still be done in $O(n^3 \log t)$ (the number of disqualified points on other planes can only change by 2 so it might be possible to rebalance in some clever way).

This approach should do better, but again I don't think it's guaranteed to have $t=k$. We can probably arrange the points so that taking the plane covering most of them sends us down the wrong path.

am attempting an answer even though the question may be somewhat unclearly stated. half of it says the points are given, the other half says that pairwise distances are given. am going to assume that point coordinates are given for this answer. there is a close connection between computing determinant and matrix rank. there is a generalization as follows. create the matrix of 3d vectors, they can be either column or row vectors. compute the rank. if it is 2, the points are coplanar. the pairwise distances can be computed from the coordinates and is not necessary to calculate/ determine matrix rank.


How to convert this DFA with multiple final states to a regular expression? (State elimination method) So I have a DFA which I would like to convert to a regular expression. As you can see it has multiple accepting states and the start state has incoming input 'a' from q2 and 'b' from q4.

I want to convert this into a regular expression using State elimination, and I know that I need to first create a new state call it 's' which replaces q0 as the start state, and then create another new state (call it 'f') which will be the new final state, and make q1, q2, q3, and q4 non-accepting states, and make epsilon transitions from the former accepting states to the new final state.

My question is, when I eliminate say q1, I don't know what the regular expression will be as a result. Now since q1 has 2 outgoing transitions 'a' to a2 and epsilon to f, what would be that regular expression? I know that for q2 it would be a(ba)a(ba) ... then q0 to f will be a(ba)*.. so far it doesn't make sense to me how this will end up becoming the correct regular expression. Am I on the right track?

When I eliminate say $q_1$, ..., now since $q_1$ has 2 outgoing transitions, '$a$' to $q_2$ and $\epsilon$ to $f$, what would be that regular expression?

Here are the transitions among the neighbors of $q_1$, which are $q_0, q_2$ and $f$ when $q_1$ is eliminated.

$\delta(q_0, ab)=q_0$
$\delta(q_0, aa)=q_2$
$\delta(q_0, a)=f$
$\delta(q_2, a+bb)=q_0$
$\delta(q_2, ba)=q_2$
$\delta(q_2, \epsilon+b)=f$

  $a(ba)^* + a(ba)^*a(ba)^*(aa(ba)^*a(ba)^*)^* + b(ab)^* + b(ab)^*b(ab)^*(bb(ab)^*b(ab)^*)*$

I am afraid the above is not correct since it does not include $abbaa$ nor $abbab$

My final answer was:

a(ba)* + a(ba)*a(ba)*(aa(ba)*a(ba)*)* + b(ab)* + b(ab)*b(ab)*(bb(ab)*b(ab)*)*

Just checking if it's right


Google's Deep Dreamer I was just wondering on a more technical side, if anyone could explain what Google does to create these amazing images from it's deep dream system.

Could anyone explain to me in a step by step way, what the program does and how it does it.

Google's Deep Dream project is research being done to visualize neural networks' learning to understand more about them.

First, you have to understand a Deep Belief Network on a high level. In short, it's a way for machines to 'learn' about data (images, in this case). That works, essentially, by transforming an input by several matrices (layers) through the network to get an output. Deep Belief Networks are trained to reconstruct their original image. All of the images are generally of some type, like animals. After some training, they begin to recognize basic features that are common between members of the training set, such as edges or colors.

The images published for the Deep Dream project are different ways of visualizing the data from trained networks. For some of the images, they observe the state of the image in layers between the input and output, resulting in artistic looking sketches of the original. For other images, they start with one image that is not related to the training set, send it through the network, then send the output through the network repeatedly to accentuate features that the network found in the image.

So, what happens in deep dream is that instead of minimizing the cost function in neural network, we try to maximize the output value of n-1/n-2 layer. And in this way we change our image, to maximize output value of n-1/n-2 layer.

Explanation

The higher layers(n-1/n-2) stores high level features information like buildings, ears of a cat etc. The lower layers (2nd/3rd) store information about edges, corners in a specific place etc.

So when we try to maximize the output of higher layers, we see more of higher level things like buildings, cats etc(this depends on what data is the model trained on earlier). In other way, we are saying we want more  cats, buildlings. So anything that lightly resembles these things, it will be made more prominent.

Similarly, when we try to maximize lower layers output, we see more of edges like things.

You can watch the following video from computerPhile to understand more about Google's deep dream.
"Deep Dream"!


Why does restricting size of input for NP complete problem imply a runtime of O(1)? I've seen this statement mentioned a few times here on cs.stackexchange and have not been able to follow the logic.  The statement is 'If you restrict the input size of the problem then solving that problem (even SAT) can be done in O(1)'.

So say I restrict the size of SAT to N = 1000, now that means that solving SAT for any N <= 1000 can be done in O(1)?  That doesn't quite follow.

Can someone shed some light on this concept?

If the input size is limited, then you can calculate the solutions to all problems. This will take a very, very, very long time. But once these solutions have been calculated, you can just lookup the solution of any problem in your list of solutions.

Even worse: Look at the definition of Big-O. The claim is that there is a constant $c > 0$, and an integer $N_0 > 0$ such that for every problem with a size $N > N_0$, the problem can be solved in less than $c * 1$ steps. If you restrict SAT to $N ≤ 1000$, then this is trivially true with $c = 1$ and $N_0 = 1001$. There are no problems with a size > 1000, therefore all the (nonexisting) problems with a size ≥ 1001 can be solved in one step.

The big O notation is to approximate to the upper bound (worst case) and gives an idea about how good is the algorithm.

O(1) is the constant-time (time of execution is known in advance) and it is the best one. The O(1) is when T(N) expression does not contain the input size N.

When restricting the size of the input N (N<=C) and as we ara approximating to upper bound, in T(N) we can replace N by its known upper bound the constant C which gives us O(1).


Does XML covers the representation of any structured data and knowledge I see nowadays XML is used to structure any file or data. It can represent both flat and hierarchical relationships. For example, it can be used to show the parse tree of a sentence in a natural language.

I am not familiar with different types of data and knowledge structures, but I would like to know if XML is theoretically the ultimate representation scheme which can model and structure any data and knowledge?

What are the reasons behind the popularity of XML?

XML is nothing more than a well-defined way to store trees of strings. Since even plain strings can encode everything you can encode in practice (i.e. countable sets), yes, XML can "model" everything.

But that's nothing special.

The popularity of XML is probably due to

it being standardized and
the amount of tool support that has developed.

There is no information-theoretic miracle involved.

Is XML the ultimate representation scheme? No:

  When the markup overhead exceeds 200%, when attributes values and element contents compete for the information, when the distance between 99% of the "tags" is /zero/, when the character set is Unicode, and when validation takes more time than processing, not to mention the sorry fact that information longevity is more /threatened/ by XML than by any other data representation in the history of computing, then SGML has gone from good kid, via bad teenager, to malfunctioning, evil adult as XML.

  As for writing SGML/XML/HTML/whatever, I have a simple way to get rid of
    the annoying verbosity of these stupid languages while retaining that
    mistake between attribute values and elements, because it is quite hard
    to make simple regular expression-based conversions retain enough data
    about an element to decide what should be attribute and element.  An
    element has the form <name [attributes] | [contents]>. Attributes have
    the form <name | value>.  Internal whitespace is only for readability.

XML                             Enamel (NML)            CL

<foo/>                          <foo>                   (foo)

<foo bar="zot"/>                <foo <bar|zot>>         (foo (bar "zot"))

<foo>zot</foo>                  <foo|zot>               (foo "zot")

<foo bar="zot">quux</foo>       <foo <bar|zot> |quux>   (foo (bar "zot")"quux")

<foo>Hey, &quux;!</foo>         <foo|Hey, [quux]!>      (foo "Hey, " quux "!")

<foo>AT&amp;T you will</foo>    <foo|AT&T you will>     (foo "AT&T you will")

<foo><bar>zot</bar></foo>       <foo|<bar|zot>>         (foo (bar "zot"))

  So I have almost none of the annoying and arbitrary quote/escape mania in
    attribute values or contents alike, either.  Entities I write as [name],
    and they end up in the Lisp version as symbols if not the character they
    represent purely for syntactic reasons.  Writing "code" in this language
    is actually amazingly painless compared to the produced noise.  Besides,
    with a few simple modify-syntax-entry calls in Emacs, I get < and > to
    match and blink and I can move up and down the structure very easily.

What are the reasons behind its popularity? Well:

  Inspired by the success of GML, the American National Standards Institute (ANSI) Committee on Information Processing assembled a team, with Goldfarb as project leader, to develop a standard text-description language based upon GML. The GCA GenCode committee contributed their expertise as well. Throughout the late 1970s and early 1980s, the team published working drafts and eventually created a candidate for an industry standard (GCA 101-1983) called the Standard Generalized Markup Language (SGML). This was quickly adopted by both the U.S. Department of Defense and the U.S. Internal Revenue Service.

  A number of industries, including the aerospace, automotive, telecommunications, and computer software industries, have been using hub languages to perform data interchange for years, and by this time the process is well understood. Typically, the major players in an industry form a standards consortium tasked with defining a Document Type Definition, which is the way in which the tag set and grammar of a markup language are defined. This DTD can then be sent with documents that have been marked up in the industry standard language using off-the-shelf editing tools, and any standard application on the receiving end can validate and process them.

  The XML solution is system-independent, vendor-independent, and proven by over a decade of SGML implementation experience. XML merely extends this proven approach to document interchange over the Web. Interestingly, the same day on which the first XML 1.0 draft was released also saw the formal announcement of an SGML initiative within HL7, the standards organization for health care IS vendors, to develop a Health Care Markup Language designed to solve exactly the kind of problem described in this example.

  Previous vertical-industry efforts have shown that capturing data in a rich markup often has benefits beyond the immediate requirements of data exchange. In a well-designed standardized patient data system, for example, specific information originally gathered in the course of a routine physical exam and tagged <allergies>, <drug-reactions>, and so on would instantly be available to alert the staff of an emergency room that an unconscious patient from a distant city was allergic to penicillin. The ability of XML to define tags specific to an area of application is critical to this scenario, because the otherwise unqualified word "penicillin" in the thousands of pages of a patient's entire medical history could not trigger the recognition that the same word inside an <allergies> element could trigger.

References

XML, Java, and the future of the Web
1.2. Where Did XML Come From? - Learning XML, 2nd Edition [Book]
Erik Naggum's XML rant
Erik Naggum on attributes in SGML/XML, Enamel (NML), Lisp
Cover Pages: SGML/XML Bibliography Part 4, I - L


Path finding under constraints Let $ G=(V,E) $ be a directed graph with a real weight function $w$ defined on the edges and $ a,b \in V$. Let $\alpha$ denote the minimal weight of all paths from $a$ to $b$ and $\beta$ denote the minimal weight of all paths from $b$ to $a$. How do you find two paths $l_1,l_2$  such that:

$l_1=(a,v_1,..,v_n,b)$
$l_2=(b,u_1,..,u_m,a)$
$w(l_1) + w(l_2)\leq 1.1(\alpha + \beta)$
From all the paths holding the above, bring to minimum the sum of weights on the edges $e=(u,v)\in l_1$ such that $(v,u)\in l_2$

Less formally, I want to find a path starting at $a$ ending with $b$ and returning to $a$ such that the path is not too long (at most 10% longer than the optimal solution) and tries to use as much as different roads as possible (if it used some road $(x,y)$ when going from $a$ to $b$ , it would try to avoid the road $(y,x)$ when going back to $a$)

One solution would be to use integer linear programming (ILP).  This is not guaranteed to have a polynomial worst-case running time (ILP can take exponential time), but ILP solvers are pretty impressive, and for reasonable-sized graphs, this might just be an effective solution in practice.

For each edge $e \in E$, let $x_e,y_e,z_e$ be integer variables with the constraint $0 \le x_e \le 1$, $0 \le y_e \le 1$, $0 \le z_e \le 1$ (so that $x_e,y_ez_e$ are forced to be either 0 or 1).  The meaning of $x_e=1$ is that $e$ is part of the path $l_1$, and the meaning of $y_e=1$ is that $e$ is part of $l_2$, and the meaning of $z_e$ is that $e$ is part of both $l_1$ and $l_2$.

Now introduce the following constraints:

$\sum_{(a,v) \in E} x_{(a,v)} = 1$ (i.e., at least one of the edges out of $a$ must be selected in $l_1$).
$\sum_{(v,b) \in E} x_{(v,b)} = 1$ (i.e., $l_1$ contains an edge into $b$).
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} x_{(u,v)} = \sum_{(v,w) \in E} x_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
$\sum_{(b,v) \in E} y_{(b,v)} = 1$ (i.e., $l_2$ contains an edge out of $b$).
$\sum_{(v,a) \in E} y_{(v,a)} = 1$ (i.e., $l_1$ contains an edge into $a$).
For each vertex $v \in V \setminus \{a,b\}$, $\sum_{(u,v) \in E} y_{(u,v)} = \sum_{(v,w) \in E} y_{(v,w)}$ (if there's an edge entering $v$, there has to be an edge leaving $v$).
$\sum_{e \in E} w(e) (x_e + y_e) \le 1.1 (\alpha+\beta)$ (condition 3 in the question holds).
For each $e \in E$, $z_e \ge x_e + y_{-e} - 1$, $z_e \le x_e$, and $z_e \le y_{-e}$, where $-e$ is the reversal of the edge $e$ (i.e., if $e=(u,v)$, then $-e=(v,u)$).  (This enforces that $z_e = 1$ if and only if $x_e = y_{-e} = 1$.)

Now minimize $\sum_{e \in E} w(e) z_e$.  This will minimize the total weight of the edges that are common to both $l_1$ and $l_2$.

You can use A* to find the least cost path from a->b and b->a, and combine those paths.

To prefer unused edges when finding the path from b->a, you can increase the weight/cost of edges that were traversed in the path from a->b.


Can Quantum Computing solve Problems not even a Turing Machine can solve? In his book "The Fabric of Reality", Penguin Books 1998, p. 218, David Deutsch says that the first quantum computer (built 1989 in the office of Charles Bennet, IBM Reasearch) "became the first machine ever to perform non-trivial computations that no Turing machine could perform".

My question: Do we really know that quantum computing is powerful enough to solve problems that not even Turing machines can solve? (Or is this just a personal belief of David Deutsch?)

While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, albeit with exponential slowdown. In particular, everything that can be computed on a quantum Turing machine can also be computed on a classical Turing machine.

The main advantage of quantum Turing machines is that they appear to solve some problems much faster than classical Turing machines. As Sasho comments, at the moment we can't quite prove this, yet this advantage is believed to hold by most researchers.

For more, check out this talk by Ashley Montanaro.

In the generality that your question is asked, the answer is YES. Quantum computation is a very wide concept. Even in non-quantum computation there are many models that go beyond Turing computability. The field is sometimes called hypercomputation. A (in my opinion) nice model are red-green Turing machines by J. van Leeuwen and  J. Wiedermann. With them you can climb up several steps in the arithmetical hierarchy. A more classical model are oracle machines.

You can define the same approches with Quantum Turing Machines, and then they compute more than a Turing machine. So again, the answer is YES, but also non-quantum models can do that.

If you only want to compare TMs to quantum TMs (which both compute only the Turing-computabel) or some other model of quantum computation, then you should refer to that model explicitly.


Primality testing: Why is dividing a number $n$ by every integer between 2 and $\sqrt{n}$ an inefficient test? In the paper "PRIMES is in P" the following is said (page 1):

  Let PRIMES denote the set of all prime numbers. The definition of prime numbers already gives a way of determining if a number $n$ is in PRIMES: try dividing $n$ by every number $m \leq \sqrt{n}$ — if any m divides $n$ then it is composite, otherwise it is prime. This test was known since the time of the ancient Greeks — it is a specialization of the Sieve of Eratosthenes (ca. 240 BC) that generates all primes less then $n$. The test, however, is inefficient: it takes $\Omega (\sqrt{n})$ steps to determine if $n$ is prime. An efficient test should need only a polynomial (in the size of the input = $\lceil \log n \rceil$) number of steps.

Firstly, isn't complexity $\sqrt{n}$ already polynomial?

Secondly, why would complexity $\lceil \log n \rceil$ represent an efficient algorithm? This seems somewhat arbitrary to me.

The complexity is measured as a function of the size of the input.
You don't have here an array of $n$ numbers but a number $n$.
 The size of the input is $O(\log n)$ (to store a number $n$ you need $\lfloor log_2(n) + 1 )\rfloor$ bits).
Hence, $O(\sqrt n)$ is not polynomial in the size of the input.

The answer to the second question is a direct consequence. Since the size of the input is logarithmic in $n$, an algorithm with logarithmic time complexity with respect to $n$ (and therefore, polynomial wrt the size of the input) would be efficient.

As an example, consider a number $M$ of size $n$, an algorithm with time complexity $O(log^k M)$ for a constant $k$, corresponds to a polynomial time algorithm (in the size of the input) of time complexity $O(n^k)$.

So what is the issue here? The algorithm clearly requires (sqrt(n)//2) divisions by the respect to the N. So if I measure complexity by the function: input number -> #of divisions, then I will get theta(sqrt(n)) complexity.

I believe the actual problem why this algorithm is inefficient that division is not a basic operation, and that the division's complexity is based on the length of divided numbers. Which I didn't see mentioned in any of the responses.

Also there seems to be a misunderstanding in expression of the complexity in "O" notation -  O(sqrt(n)) is a subset of O(n) and therefore the algorithms should be more efficient, because power of 0.5 will be less than power of 1 for all positive integers. The other thing is that all algorithms with this (sqrt) complexity can be implemented only in such a way you showed - why is that inefficient. But I state that O(sqrt(x)) <= O (x).


Is there an O(logN) optimal weight balanced binary search tree where weights/sizes of left and right subtree differ at most by 1? I am wondering if there is a log time WBT (weight balanced binary search tree) data structure in which for any node, the sizes of its left and right subtrees diff at most by 1.

PS: I have read through Balancing weight-balanced trees but the weights of subtrees can differ up to a factor of $\Delta$.

Refer the following paper; https://www.researchgate.net/publication/2241064_A_New_Weight_Balanced_Binary_Search_Tree.
It has both bottom-up and top-down restructuring.


Is IEEE 754 float arithmetic associative, commutative, distributive, etc? Why? Does the associative/commutative/distributive/etc property hold for arithmetic performed with IEEE 754 floats?

Obviously the answer is no to most of those questions, but do any of the properties of standard arithmetic hold? How can one formulate proofs (or at least proof-like statements) explaining why any particular property does or does not hold?

The IEEE 754 standard defines exactly how floating-point arithmetic is performed. For many interesting theorems, you will need to examine the exact definition. For some less interesting ones, like a+b = b+a or ab = ba, all you need to know that IEEE 754 always calculates the exact result, rounded in a deterministic way. For non-theorems, like (a+b)+c = a+(b+c), which is false, all you need is a counterexample which is usually easy to find.

Check e.g. Goldberg's "What every computer scientist should know about floating point". Heavy reading, but a must.


Sub language is not Turing-recognizable, or could it be? Let A and B be languages with A ⊆ B, and B is Turing-recognizable. Can A be not Turing-recognizable? If so, is there any example?

This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^*$ and any other language is between them w.r.t. set inclusion.

Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.

In this case A couldn't be Turing-recognizable.
Take this as an example:

language B is the union of a language t.r (C) and a language not t.r(A).
you can create a turing machine that recognizes B.
A is not t.r and A ⊆ B.

is that right? i dont know if it is..so.. =)


Proving that an $n$-element heap has at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes I am having trouble proving that an n-element heap can have at most $\lceil \frac{n}{2^{h+1}-1} \rceil$ nodes.

Please note that I am proving a loose bound.

First I proved that a complete binary tree can have at most $2^{h+1} - 1$ nodes. However, I don't know how to use this fact to inductively prove the formula above?

The only thing thus far in my inductive proof is showing the base case ($h=0$), which is trivial.

Probably, you mean this:
A heap of size $n$ has at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes with height $h$.

Proof can be found for example here:
http://www.cs.sfu.ca/CourseCentral/307/petra/2009/SLN_2.pdf

This is the actual question should be (Coreman 6.3-3) :A heap of size n has at most ⌈n/2^(h+1)⌉ nodes with height h.

This is just a simple intution for the proof.

This is an easy to prove property of complete binary tree/heap that is
no. of leaf nodes = (total nodes in tree/heap)/2 {nearly}

Now, no. of nodes at height 0 = n/2 (because all leaf nodes are at maximum depth)

So traversing from bottom to top of tree, the height keep on increasing height by one, at each level we have no. of nodes = (no. of nodes from root to that level)/2, and once we finished counting that level we're left with same problem for half of the total node upto this level, for a level above (Think recursively, at each step although increasing the height, but deleting leaf nodes, and redoing the problem with 1/ of the nodes).

Therefore, no. of nodes at :
At height 1 = (n/2)/2 = n/4,
At height 2 = (n/4)/2 = n/8,
.
.
.
At height h = n/2^(h+1) {observing the trend}


TSP Variant --- Colored Path Recently I came up with a traveling-salesman-esque problem. As usual, we have $n$ vertices, and a weighted edge between any two vertices. However, each vertex is associated with a color, which may be repeated. Then, you are given a sequence of colors, and you want to find the shortest path that follows this sequence. If all vertices are the same color, this is the same as TSP. However, if all vertices are different colors, there is only one solution.

Is this variant at all studied? Let $c$ be the maximum number of vertices which are the same color. Is the decision problem this variant NP-complete for some fixed, $c$, or alternatively is there a simple way to solve the decision problem polynomially for any finite $c$? Alternatively, one can bound $k$, the mamximum amount of times a given color appears in your path.

For $k=1$, it is polynomial. WLOG we can assume the path goes through colors $1,2,3,\ldots,x$. For each vertex of color 1, we consider each edge to a vertex of color 2. We keep track of the shortest path from color 1 to each vertex of color 2. Rinse and repeat for each color. This only requires $|\mathrm{color}\  i||\mathrm{color}\  i+1|$ additions and comparisons to get the shortest paths to each vertex of color $i+1$.

Additionally, I realize $k$ only matters if it is less than $c$, so bounded $c$ is polynomial if bounded $k$ is polynomial and bounded $k$ is NP-Complete if bounded $c$ is NP-Complete.

In this answer we prove the colored path problem is NP-hard for $c\ge 7$. I don't know whether it is NP-hard for $2\le c\le 6$. Without loss of generality, we prove the NP-hardness for  the Hamiltonian Path problem variant, i.e., asking whether there exists such a colored Hamiltonian path, insteand of the TSP variant.
We use the normal reduction from 3SAT (with $n$ variables and $m$ clauses) to Hamiltonian Path with the following changes:

For each variable, we only have $2m$ nodes: $v_1,v_2,\ldots,v_{2m}$. The $i$th clause corresponds to nodes $v_i,v_{i+1}$ and $v_{2m-i+1},v_{2m-i}$, i.e., if the $i$th clause contains the positive literal of this variable, we have the path $v_i\rightarrow c_i\rightarrow v_{i+1}$, where $c_i$ is the node corresponding to the $i$th clause; and if the $i$th clause contains the negative literal of this variable, we have the path $v_{2m-i+1}\rightarrow c_i\rightarrow v_{2m-i}$. In addition, we add a blank node $b_i$ between $v_i$ and $v_{i+1}$.

For each variable, for each $i$, we give $v_i$ and $v_{2m-i}$, $b_i$ and $b_{2m-i}$ the same color. In addition, we give $c_i, b_i, b_{2m-i}$ the same color if the variable is contained in the $i$th clause.
The following graph is constructed from $(x_1\vee \neg x_2\vee x_3) \wedge(x_2\vee \neg x_3\vee \neg x_4)$. The number above a node represents its color.

We remove the edges to the sink node $t$. Instead, we add paths that pass through the blank nodes that may potentially not be visited due to visits of clause nodes. In the example above, the added edges form the following structure.

In the example above, we ask whether there is a Hamiltonian path with colors 1-2-3-4-5-4-3-2-6-3-7-8-7-3-6-...-11-3-8-14. You can check this reduction indeed works.

It is NP-complete.

It is obviously in NP.

To show it is NP-hard, reduce TSP to your problem. Say you require to repeat a certain sequence of colors. Just take the TSP instance and replace edges by paths with the repeat pattern of colors. Then the only legal way to move from one vertex to the next is by traversing that path.


Is it NP hard to decide whether there exists a subset of V of size at most $k$ hitting all maximal bicliques of G? The following problem is from my algorithms class:

  Given a graph $G(V, E)$, a set $C \subseteq V$ is called a biclique iff  $G[C]$ is a complete bipartite graph, where $G(C)$ is the subgraph induced by $C$. A biclique is called maximal if it is not a subset of a larger biclique. Then our problem asks whether there exists a subset of $V$ of size at most $k$ hitting all maximal bicliques of $G$, i.e., can we find $k$ vertices in $V$ such that every maximal bicliques of $G$ cantains at least one vertex of these $k$ vertices. Prove the problem is NP hard.

I'm trying to prove
$$\text{Vertex-Cover} \le_p  \text{This-Problem}$$
but haven't came up with a solution until now. Could anyone help me out here?

Is an independent set a biclique?

After figuring out the first reduction from Vertex Cover (VC) described below, I realised that I had assumed that a biclique has at least one vertex in each part (and thus at least one edge).  But in many ways it makes more sense to consider an independent set (IS) to be a biclique too: it is a complete bipartite subgraph induced by two disjoint vertex subsets $A$ and $B$ -- it just happens that one of the subsets is empty -- so it (vacuously) meets the criteria.  (Similarly, a one-vertex graph is still considered a bipartite graph, and still considered a clique.)  I could not quickly find a "standard" definition to confirm either possibility, so I'll first give a reduction that considers only complete induced bipartite subgraphs with both vertex sets nonempty to be bicliques, and then describe how to modify the construction when independent sets are also considered to be bicliques (which turned out to be much trickier).

I'll call the problem in question "Maximal Biclique Hitting Set" (MBHS).  A biclique that contains at least one edge (i.e., is not an IS) is an "edgy" biclique.

Reduction from Vertex Cover for "edgy" bicliques

The following construction builds a MBHS instance $(G' = (V', E'), k')$ that replaces every edge in the input graph $G = (V, E)$ with a "rectangle" in which the two pairs of diagonally opposite vertices form a 4-vertex maximal biclique.

Add all vertices and edges in $G$ to $G'$.  For every edge $uv$ in $E$, create two new vertices $x_{uv}$ and $y_{uv}$ in $G'$, and the three edges $x_{uv}y_{uv}$, $uy_{uv}$ and $vx_{uv}$.  Set $A_{uv} = \{u, x_{uv}\}$ and $B_{uv} = \{v, y_{uv}\}$ and observe that $(A_{uv}, B_{uv})$ forms a biclique with 2 vertices in each part.

To see that this biclique is maximal, consider any other vertex $z \in V' \setminus \{u, v, x_{uv}, y_{uv}\}$.  To be able to add $z$ to $A_{uv}$ to form a larger biclique $(A_{uv}', B_{uv})$, $z$ must be adjacent to both $v$ and $y_{uv}$ -- but by construction, the only vertices adjacent to $y_{uv}$ are $x_{uv}$ and $u$, and $z$ is not either of those.  Similar reasoning shows that $z$ cannot be added to the other side ($B_{uv}$) either.  Since $z$ was arbitrary, $(A_{uv}, B_{uv})$ must be a maximal biclique.

Finally, set the threshold parameter $k'$ for the MBHS instance to $k$.  This concludes the construction.  I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k'$.  The VC directly gives a solution to the MBHS instance, since every maximal biclique in $G'$ (both the rectangle bicliques that we created, and any bicliques already present in $G$) contains some edge of $G$, and every edge of $G$ contains at least one vertex in the VC solution.

If there is a solution to the constructed MBHS instance of size at most $k'$, then there is a solution to the original VC instance of size at most $k$.  Assume there is an edge $uv$ in $G$ whose corresponding edge in $G'$ is not covered (i.e., neither of its endpoint vertices is in the MBHS solution), since otherwise we are already done.  Let $(\{u, x_{uv}\}, \{v, y_{uv}\})$ be the unique rectangle maximal biclique that contains $uv$ in $G'$: then it must be that at least one of $x_{uv}$ or $y_{uv}$ is in the MBHS solution, since there is no other way to hit this biclique.  Replace whichever one of these two vertices is in the solution (choose arbitrarily if both are) with either $u$ or $v$ (again, choose arbitrarily) to create a new MBHS solution of the same size (at most $k$) with one more $G$-edge covered.  This can be repeated until every edge in $G$ is covered by a vertex in the MBHS solution, which remains of size at most $k$.  Finally, discard any remaining "rectangle vertices" (vertices not in $V$) from the solution, leaving a VC of size at most $k$.

When independent sets are considered bicliques too

If independent sets are also bicliques, the construction above can fail, most obviously on a graph containing vertices but no edges (which has a single maximal biclique, but an empty VC).

Create $|V|+1$ copies of $G'$ (that is, of the graph constructed for the reduction for edgy maximal bicliques).  Call this new graph $G''$.  The key observation is that in $G''$, there are $|V|+1$ copies of each maximal edgy biclique in $G'$ that all need to be hit separately, but a set of vertices that hits every maximal IS in a single copy of $G'$ suffices to hit every maximal IS in $G''$.  (There are actually vastly more maximal ISes in $G''$ than in $G'$, since to form a maximal IS in $G''$, we may independently choose a maximal IS from each copy of $G'$.  But an IS in $G''$ cannot be maximal unless it includes some $G''$-IS in each copy -- so it suffices to choose a particular copy and hit every maximal IS in that copy.)

Let $k''$ be the threshold parameter that together with $G''$ forms the constructed instance of MBHS.  Set $k'' = k(|V|+1) + |V|$.  Essentially this allows us to spend $k$ vertices hitting edgy maximal bicliques in each of the $|V|+1$ copies of $G'$, plus up to $|V|$ vertices to hit maximal ISes.

That ends the description of the construction.  I'll now show that the constructed MBHS instance is a YES-instance if and only if the original VC instance is a YES-instance:

If there is a solution to the VC instance of size at most $k$, then there is a solution to the constructed MBHS instance of size at most $k''$.  To see this, first replicate the VC solution across all $|V|+1$ copies of $G'$ in $G''$: these vertices hit every edgy maximal biclique for a cost of $k(|V|+1)$.  Now add every remaining vertex from the first copy of $G'$ to the solution, ensuring that we hit every maximal IS in that copy of $G'$, and thus every maximal IS in $G''$ overall, for at most $|V|$ more vertices.  Every maximal biclique is now hit and we have used at most $k(|V|+1) + |V| = k''$ vertices.

If there is a solution to the constructed MBHS instance of size at most $k''$, then there is a solution to the original VC instance of size at most $k$.  By the pigeonhole principle, at least one of the $|V|+1$ copies of $G'$ has at most $k$ vertices in the solution.  These $k$ vertices necessarily hit all edgy maximal bicliques in that copy, since there is no other way to hit these bicliques, and so can be transformed into a solution to the original VC instance of size at most $k$ in the same way as described earlier for the "edgy bicliques" version of the reduction.

Obviously all steps can be carried out in polynomial time, so the MBHS problem is NP-hard.  (It's not clear to me that it is in NP though -- there could be exponentially many maximal ISes (consider a $3n$-vertex graph consisting of $n$ vertex-disjoint triangles), so checking that each one is hit takes too long.  Does anyone have thoughts on a certificate that can be checked in poly-time?)

Bonus material: A failed reduction attempt

My first attempt at dealing with non-edgy bicliques was to add one new vertex $p$ to $G'$, and connect it to every other vertex in $G'$: Now every maximal independent set originally in $G'$ becomes a maximal biclique with $p$ on one side, and intuitively it seems that it would be a good idea to include $p$ in the MBHS solution, as it would hit every such biclique for the cost of just 1 vertex.  The problem is that it could be that every maximal IS in $G'$ is already hit by some vertex in the VC, meaning that it is not actually necessary to include $p$, and that doing so would therefore yield a suboptimal solution.  (This can happen when the given threshold $k$ is loose; in particular, it will always happen for $k=|V|$.  If OTOH $k$ is the minimal threshold for which the answer to the VC problem is YES, then at least one maximal IS misses every vertex in the VC solution, and we would be justified in forcing $p$ into the solution -- but we don't know whether this is the case at the point when we are mapping the VC instance to the MBHS instance, and it is NP-hard to find out!)  The general approach here, of trying to design a gadget that will cause all ISes in $G'$ to become edgy bicliques, can be expressed precisely as: Find a small graph that has an optimal MBHS solution with the additional property that every maximal IS in the graph is hit by some vertex in the solution.  But after trying several examples with 2, 3 or 4 vertices, I wasn't able to come up with such a gadget.

Transformation from Hitting Set to this problem.
In the Hitting Set problem, we are given a collection $C=\{S_i\}$ of subsets of a universal set $U$ and an integer $k$, the question is that if one can choose $k$ elements of $U$ to hit all the subsets. The Hitting Set problem can be described as a bipartite graph $B=(U\cup C,E)$. We may add the following constraint without affecting its NP-completeness: $S_i \not\subseteq S_j$ for any $S_i, S_j\in C$.
By this constraint, each $S_i$ and its members form a maximal biclique. On the other hand, a vertex subset hitting all $S_i$ clearly hits all the maximal bicliques. That is, a vertex subset $H$ hits every maximal biclique if and only if $H$ hits every $S_i$ in $C$. To complete the reduction from Hitting Set to this problem, it is easy to show that if there are $k$ vertices in $U\cup C$ hitting all $S_i$, then there are $k$ vertices in $U$ hitting all $S_i$.


Context-free grammar for language with unequal numbers of a and b I've been trying to get a CFG for the language of all words with unequal numbers of a and b, i.e.

$$\{u \in \{a, b\}^* \mid \text{number of occurrences of $a$ and $b$ in $u$ are unequal} \},$$

but it seems that I keep getting specific cases instead of the general case.

Here are some that I have tried:

(S being the start Variable)

S -> A | a | b
A -> aV | bT
V -> aV | bL
L -> aV
T -> bT | aM
M -> aT

This one's problem is that you can't create 2 of the same string if it's the lesser amount of alphabet.

So I've tried

S-> A | B
A -> aV | a
V -> aV | aVb | bVa
B -> bT | b
T -> bT | aTb | bTa

This one also has problem because if you have a you need to have b on the opposite end.

Additionally, I know this is one of the huge problem in my process is that you start with 'a' or 'b' and use that as a flag for if there is more 'a' or there is more 'b'...

I've been trying to think the way where you can input an alphabet (i.e S -> aV | bV) so that I can start with any variable and I use cases or condition to go to different variable, but I end up with infinite variable situation.

Here are some hints:

Break the language into two parts: $L_a = \{ w : \#_a(w) > \#_b(w) \}$ and $L_b = \{ w : \#_a(w) < \#_b(w) \}$. Below we concentrate on $L_a$.
Figure out a grammar for the language $L_= = \{ w : \#_a(w) = \#_b(w) \}$. Here the idea is that $L_= = (aL_=b + bL_=a)^*$.
Use the identity $L_a = L_=(aL_=)^+$ to construct a grammar for $L_a$.

I know this is like a very old post, (and way past your homework deadlines), but here's the solution:

$\qquad\begin{align*}
  L &\to L_a \mid L_b \\
  L_a &\to L_=aL_a \mid L_=aL_= \\
  L_b &\to L_=bL_b \mid L_=bL_= \\
  L_= &\to aL_=bL_= \mid bL_=aL_= \mid \varepsilon
\end{align*}$


Find a MST such that it's mostly red (original graph's edges are colored red and blue) Consider the following problem:
Given a simple, strongly-connected, weighted graph G=(V,E), of which every edge is colored either red or blue (in addition to having a numeric weight).
Find an efficient algorithm to find an MST which is mostly red (meaning, has the most red edges possible).

I think this can be done in linear time, in O(n+m) complexity using either Kruskal or Prim's algorithms, but I can't find an algorithm to do that.

I thought about diving the edges into two groups - red and blue, and then running Kruskal's algorithm on the red edges first, and then if we still don't have |V|-1 edges in the MST we have so far, run Kruskal again on the blue edges.
However, this algorithm doesn't solve the given problem since we might not end up with a tree, but rather with a forest (made up of two trees).

Please advise.

Hint: Add $\epsilon>0$ to the weight of all blue edges. (This is equivalent to the suggestion Raphael made in his comment.)

Approach 1: Use a disjoint set structure, every vertex will be a set, then connect all the vertices with the red edges first, and then add the blue edges. Linear time.

Approach 2: Second approach, weight of red is 0 and weight of blue is 1. Run Prim algorithm. it is linear because you don't have to sort the edges.


How to approach Vertical Sticks challenge This problem is taken from interviewstreet.com

We are given an array of integers $Y=\{y_1,...,y_n\}$ that represents $n$ line segments such that endpoints of segment $i$ are $(i, 0)$ and $(i, y_i)$. Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, $v_1, ..., v_n$, where $v_i$ is equal to length of ray shot from the top of segment $i$. We define $V(y_1, ..., y_n)
= v_1 + ... + v_n$.

For example, if we have $Y=[3,2,5,3,3,4,1,2]$, then $[v_1, ..., v_8] = [1,1,3,1,1,3,1,2]$, as shown in the picture below:

For each permutation $p$ of $[1,...,n]$, we can calculate $V(y_{p_1}, ..., y_{p_n})$. If we choose a uniformly random permutation $p$ of $[1,...,n]$, what is the expected value of $V(y_{p_1}, ..., y_{p_n})$?

If we solve this problem using the naive approach it will not be efficient and run practically forever for $n=50$. I believe we can approach this problem by indepdently calculating the expected value of $v_i$ for each stick but I still need to know wether there is another efficient approach for this problem. On what basis can we calculate the expected value for each stick independently?

Imagine a different problem: if you had to place $k$ sticks of equal heights in $n$ slots then the expected distance between sticks (and the expected distance between the first stick and a notional slot $0$, and the expected distance between the last stick and a notional slot $n+1$) is $\frac{n+1}{k+1}$ since there are $k+1$ gaps to fit in a length $n+1$.

Returning to this problem, a particular stick is interested in how many sticks (including itself) are as high or higher. If this number is $k$, then the expected gap to its left is also  $\frac{n+1}{k+1}$.

So the algorithm is simply to find this value for each stick and add up the expectation.  For example, starting with heights of $[3,2,5,3,3,4,1,2]$, the number of sticks with a greater or equal height is $[5,7,1,5,5,2,8,7]$ so the expectation is $\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 15.25$.

This is easy to program: for example a single line in R

V <- function(Y){ (length(Y) + 1) * sum( 1 / (rowSums(outer(Y, Y, "<=")) + 1) ) }

gives the values in the sample output in the original problem

> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15

I dont really understand what do you demend, from tags it seems you are looking for an algorithm.

if so, what is the expected time complexity? by saying: "If we solve this problem using the naive approach it will not be efficient and run practically forever for n=50." it seems to me that your naive approach solves it in exponential time.

i do have a O(n^2) algorithm in mind tho.

assume int y[n], v[n] where v[i] initialized with 1; as described in the question
for (i=1;i<n;i++)
   for ( j=i-1 ; j>=0 && y[j]<y[i] ; j--) v[i]++;