An algorithm is presented for the exact solution of the evolution of the density matrix of a mixed quantum-classical system in terms of an ensemble of surface hopping trajectories. The system comprises a quantum subsystem coupled to a classical bath whose evolution is governed by a mixed quantum-classical Liouville equation. The integral solution of the evolution equation is formulated in terms of a concatenation of classical evolution segments for the bath phase space coordinates separated by operators that change the quantum state and bath momenta. A hybrid Molecular Dynamics-Monte Carlo scheme which follows a branching tree of trajectories arising from the action of momentum derivatives is constructed to solve the integral equation. We also consider a simpler scheme where changes in the bath momenta are approximated by momentum jumps. These schemes are illustrated by considering the computation of the evolution of the density matrix for a two-level system coupled to a low dimensional classical bath. (C) 2000 American Institute of Physics. [S0021-9606(00)50215-3].