  We initiate the study of computing shortest non-separating simple closed
curves with some given topological properties on non-orientable surfaces.
While, for orientable surfaces, any two non-separating simple closed curves are
related by a self-homeomorphism of the surface, and computing shortest such
curves has been vastly studied, for non-orientable ones the classification of
non-separating simple closed curves up to ambient homeomorphism is subtler,
depending on whether the curve is one-sided or two-sided, and whether it is
orienting or not (whether it cuts the surface into an orientable one).
  We prove that computing a shortest orienting (weakly) simple closed curve on
a non-orientable combinatorial surface is NP-hard but fixed-parameter tractable
in the genus of the surface. In contrast, we can compute a shortest
non-separating non-orienting (weakly) simple closed curve with given sidedness
in $g^{O(1)}.n\log n$ time, where $g$ is the genus and $n$ the size of the
surface.
  For these algorithms, we develop tools that can be of independent interest,
to compute a variation on canonical systems of loops for non-orientable
surfaces based on the computation of an orienting curve, and some covering
spaces that are essentially quotients of homology covers.
