This is an outline for the talk on the stable marriage problem on November 7:

 1. Definition of  Stable marriage problem
 2. Gale Shapley proposal algorithm and it's properties including 
     1. running time
     2. stable match,
     3. male and female optimal stable marriage
 3. definition of weakly, strongly, super stable
 4. Random algorithm and its running time 

Reading : 

http://www.ceid.upatras.gr/courses/pithmeth/slides/lecture5.pdf

http://is.muni.cz/th/172646/fi_m/master.pdf