On the Role of Proofs in a Course on Design and Analysis of Algorithms

摘要

This paper discusses the role of proofs in a course on design and analysis of algorithms. It argues that correctness proofs should always be considered as an integral part of algorithmic solutions, which should otherwise be considered as incomplete. Proofs and proof strategies should be emphasized in such a course, and active proof production should be required of students. Such an emphasis can improve mathematical as well as algorithmic skills, and can demonstrate the important and unique role of mathematics within computer science.