Natural Sciences

MATH|COM 306: Discrete & Algorithmic Mathematics Syllabus

Course Description and Goals: One of the possible conceptual divisions of mathematics is into the two branches: Discrete and Continuous Mathematics. Continuous Mathematics is the mathematics of continuous functions and embraces Integral and Differential Calculus. Discrete Mathematics can include countable structures (combinatorics), probability, sets, matrices, Trees and Graphs which are entities (vertices) connected by paths (sometimes called edges) and systems of mathematical logic such as induction or Boolean Algebra. Although the division of mathematics into Discrete and Continuous branches is convenient, the boundary between the two is not tight: the techniques of one branch are often relevant to the other. It may be impossible to place some mathematical subjects (such as Modern Algebra or Topology) in only one of these branches.

The mathematics used in computer design and software applications, perhaps by the very digital rather than analog nature of computing machines, primarily belongs to Discrete Mathematics. For the student interested in computing systems, therefore, Discrete Mathematics is a variously defined body of mathematics essential to their interests and is prerequisite to most computing courses above COM 202. For the student more interested in mathematics, the applications of Discrete Mathematics are Algorithmic in nature (elegant recipes that are best if they solve a problem not only correctly but quickly and within available resources.) For all but the most trivial real-world problems, Discrete Mathematical applications are solved by design of a computer algorithm, implemented in a modern computer language, and made available for computer processing whenever problems fitting the same pattern arise.

This course uses the approach of joining mathematical theory to application by using algorithmic implementation. Some algorithms from the text or developed in student exercises will be translated from the pseudocode of the algorithm into a high-level computer language, compiled and tested with sets of data. Because Discrete Algorithmic Mathematics is diverse in its scope, the course and text begin by reviewing several areas of mathematical preliminaries (Chap. 0). This material has the primary purpose of preparing students with a variety of backgrounds for the course, but also in its own right is a valuable beginning to the study of Discrete Mathematics. Sets, functions, mathematical logic and matrix algebra are reviewed here. A brief introduction to the nature and implementation of algorithms is followed by a discussion of mathematical induction. (Because Discrete Mathematics deals with discrete, countable, and often sequentially ordered things, induction from the case of (n-1) things to n things becomes a powerful technique.) More complex ordered structures are explored using Trees and Graphs. Counting methods leads to a discussion of counting the permutations and combinations of usually unordered things. The course ends with a further discussion of mathematical logic and one of its aspects, Boolean Algebra. Boolean algebra is the algebra of logic problems, whether of the software or of the digital circuits that comprise a computer.

The course is a “Designated Critical Thinking Course” and will have as a major goal the enhancement of your critical thinking skills. These skills extend beyond the proper manipulation of expressions by the rules of mathematics or the syntax of a computer language. They include developing the habits of logical thought in such a way that care in logical argument pervades your approach to decision making in the personal and social sphere as well as within your academic concerns. As we learn the distinctions between valid, true and sound arguments, you will be asked to apply those distinctions outside Discrete Mathematics and will do so in a series of essays. You will find examples of false or unsound but valid arguments in the social or political world (e.g., environmental or health policy decisions.). We will also distinguish between deductive logic and two forms of inductive reasoning. One type of induction, mathematical induction, you will learn to use as a means of proof (such proofs often lead to important recursive algorithms.) What is also called inductive reasoning cannot be used for proof, but as a means of suggesting a new and fruitful hypothesis or theory. As part of the critical thinking component of the course, you will describe examples of deduction and the two forms of induction outside of mathematics. We will also explore tautologies without which mathematics would have little development, but of often empty usefulness in the social sphere. You will describe examples of tautologies inside and outside mathematics and reflect on the misuse of the latter.