Concrete Mathematics is (as it says itself) intended for first year grad students. It is certainly good, but it is NOT for a "complete noobie". I am in a similar situation, and am finding Vellman's "How to Prove It" extremely useful. Having poked around the edges of math for about a year, I finally realized that proofs are central to mathematical maturity... No more eyes crossing when I read a new CS textbook!