Currently, I'm delving into Analysis of Algorithms and I've discovered that I would need to improve my knowledge of Probability Theory. Any recommendation? Where do I start? Thanks in advance!
The best intro probability book ever written is available online from MIT open courseware.
Old editions of standard textbooks are usually easy to get cheap. You might try Sheldon M. Ross; A First Course in Probability, a 5th edition from 1997 can be found for less than \$5 at Abe Books (or Powell's, or Zubal). Another old standard is Jay L Devore; Probably and Statistics for Engineering and the Sciences, with similarly low prices for old used editions. (This is the secret of the textbook industry: they churn out new editions with slightly different homework problems every couple of years, so that the students need to buy new editions for way too much money. The result is that if you want a book but don't need it for the homework assignments you can get it for next to nothing.)
Finally: there are the recommendations from James M. Cargal's page of Recommended Books in the Mathematical Sciences. I've used his recommendations as a starting point for several investigations into areas of mathematics where I wanted remedial help.
I highly recommend Mitzenmacher and Upfal, Probability and Computing.
It has almost all the background needed for a beginning graduate student to start in probabilistic algorithms and analysis, and is clearly written, nice examples, etc.