Catalog description Application of formal methods to discrete analysis—mathematical induction, the correctness of algorithms, relations and functions, combinatorics, analysis of algorithms. Application of formal methods to the modeling of discrete structures of computer science—graphs, binary trees.
Objective As this course is a continuation of Math 220 the objective is the same. Specifically, the philosophy of this course is expressed well by Robin Milner, the 1992 Turing Award winner, in an interview printed in Communications of the ACM , January, 1993:
The best thing to do, whether you’re of a theoretical or a practical bent, is to treat the subject as neither purely theoretical or purely practical. The worst thing you can do is to follow your bent, which would probably be on one of those sides, and ignore the other side. The whole richness of the subject comes from the interplay between practice and theory.
Many will pretty soon find themselves ignoring one of those components because they will naturally become very applications oriented or very basic-research oriented. But the longer we can keep the link between the theoretical frontier and the practical frontier, the better the whole thing will be. We should encourage the next generation to respect that link. If you don’t respect that, you lose a whole degree of freedom in the interest of the subject.
Both mathematics and computer science are based on logic as a tool to establish truth through various techniques of proof. The objective of this course is for us to learn formal logic as a theoretical foundation and its application to topics in discrete mathematics and computer science.