Why should a CS degree contain a course on discrete mathematics?
- Computing systems comprise of computing, storage and communication subsystems that are combined in multiple ways using complex usage descriptions (known as code or software) to achieve defined purposes e.g. find the square root of a number, provide real-time traffic and routing information, find the average of a set of numbers etc.
- For each such purpose, let us call it an application, a specification is provided and an inventory of resources is known (i.e. what machines, bandwidth, energy supply, time etc are available.)
- For a particular implementation of a computing system to be acceptable it must (a) correctly fulfill the application specification and (b) be able to perform its tasks within the available resources.
- Before a particular implementation of a computing system is adopted we must be able to rigorously verify, to the extent possible, that it meets requirements (a) and (b) above.
- Since the computing resources available to us are (generally) finite and all computing is done on domains that are finite (or countable), the mathematics of discrete sets is applicable to build rigorous arguments to justify the correctness and efficiency (req (a) and (b)) of a particular implementation.
What should your learning goal(s) be?
There is a lot of debate about what should or should not be covered in such a class. However, the main learning goal is this:
- At the end of this class the student should know what a rigorous proof is, i.e.,
- you should be able to identify if an argument is a rigorous proof or not, and,
- for a given mathematical statement you should understand whether your justification for it constitutes a rigorous proof or not.
Amitabha Bagchi. Thu Jul 18 16:46:53 IST 2019