This course integrates discrete mathematics with algorithms and data structures, using computer science applications to motivate the mathematics. It is designed to be taken simultaneously with Computer Science 15, 18, or 19. However students who are unable to complete it in this way may take it after Computer Science 15,18, but before Computer Science 25.
The course introduces counting techniques and number theory, with an emphasis on the application to RSA public key cryptography. It covers logic and proofs, including mathematical induction. Relationships among recursive algorithms, recurrence relations, and mathematical induction are discussed with particular attention to trees as a recursive data structure. Issues of expected running time for algorithms and the technique of ³hashing² data files for quick recovery of information guides the discussion of probability through independent trials experiments and expected values. The course also covers matrix algebra, motivated by how linear transformations are used in computer graphics and (time permitting) in error correction codes.