Is $O(N+M)$ exponential or polynomial?
Exponential or polynomial in what? As stated, it's clearly polynomial in $M$ and $N$.

The complexity of algorithms is given in terms of the length of the input. If an algorithm receives $M$ and $N$ as input, written in binary, then $M+N = O(2^\ell)$, where $\ell$&nbsp;is the length of the input in bits.

You should ask your professor for clarification. S/he knows what s/he actually said and what the context was; we're just guessing.