We present a two-qubit Deutsch-Jozsa algorithm with single photons generated in a single InP(GaInP) quantum dot. The two qubits are implemented using a dual-rail representation and the polarization state of a single photon. We could obtain a fidelity of up to 79%. Since the success probability of our computation is limited by phase-noise in an interferometric setup, we use noise-resistant encoding in appropriate superpositions of spatial modes.