Oops, sorry! Cryptocoryne are a species of plant, popular ones include Cryptocoryne beckettii, C. Balansae, C. Wendtii, C. Parva, but there's all sorts out there. They're not as quick growing as stems, but I personally love the darker hues and different textures. They don't do well with swings in parameters or temperatures though, and are notorious for "Crypt melt" in which all their leaves melt and they pretend to die while they actually adapt to new surroundings.
I believe you can get heating pads for small tanks even, but have never used them myself. I'd be really interested to follow along if you do use them though, as I've read somewhere that some plants (including cryptocorynes) grow much faster when their roots are in warmed sand. No idea if that's true though...
Re: the shrimps - Don't get me wrong, it definitely *can* be done, I guess it's just down to personal preference. Although I probably wouldn't personally do it, a 1 gallon with shrimp is FAR better than some of the set ups with bettas etc. that you see a lot, and the shrimp would probably be fine.
Just as an aside, seeing as you said you were new to it - water doesn't contain much beneficial bacteria as they're photophobic and like to attach themselves to surfaces. So it's your filter that's where all the good stuff is at!