Can we still use conjugate gradient descent when we don't know the Hessian matrix? Say a function $f$ can be approximated by 
$$f(x) = a + x^Tb + \frac{1}{2}x^TAx$$
at some point $x$. $a, b \text{ and } A $ are constants, I want to minimize $f$ with respect to $x$ without constraint.
I just learned conjugate gradient algorithm (GGA) from this set of slides, it seems we cannot use GGA for minimization without knowing the matrix $A$. However, in many cases, it is impractical to calculate this $A$ (which is the Hessian matrix of $f$), can we still use GGA for minimizing $f$? 
 A: The conjugate gradient method does not require the Hessian matrix (as in Newton's method) or even an approximation of it (as in quasi-Newton methods). This makes it a good choice when the Hessian is unavailable, or the number of parameters is very large.
On each iteration, the parameters are updated by performing a line search along the current search direction. The initial search direction is the negative of the gradient (i.e. steepest descent direction, as in gradient descent). On subsequent iterations, the search direction is given by the negative gradient plus some fraction $\beta$ of the previous search direction (this can be seen as similar to gradient descent with an adaptive momentum term). $\beta$ is calculated so as to maintain conjugacy between subsequent search directions. Various rules are possible for calculating $\beta$ (e.g. Polak-Ribiere is a popular variant). Conjugacy will eventually be lost, so the search direction must periodically be reset to the steepest descent direction.
This algorithm is covered in the last several slides of the presentation you posted. Also, take a look at the Wikipedia article linked above.
