Objectives and Contextualisation

Discrete Mathematics is a field of mathematics that studies finite mathematical objects. It covers topics such as combinatorics, graph theory, cryptography, error-correcting  codes, combinatorial design theory, game theory, logic, optimization, or algorithm design and analysis that can be applied to solve problems in any of the above-mentioned branches. Most of discrete mathematics has evolved relatively recently, motivated by the challenges mainly in computer science and operations research. The chapters of this introductory course are quite independent from one another. A prior knowledge of linear algebra, modular arithmetic, basic combinatorics, and -fundamentally- mathematical language and reasoning should be adequate to understand the subject matter of each chapter.

The first chapter addresses the topic of generating functions and recurrent sequences, this being a natural next step following the elementary combinatorics studied in the first year course Fundamental Mathematics. Once again, problems in combinatorics require training the skill of formulating a problem in terms of a mathematical statement. The second chapter deals with graphs,  which are a fundamental tool for problem solving in quite different settings, ranging from the most abstract mathematics up to operations research. In some cases, a graph-theoretical formulation of the problem turns out to be, in itself, illuminating and a highly efficient step towards the solution.

The last chapter tackles the topic of linear programming, whose goal is to optimize linear functions of several variables subject to linear constraints. Although the subject  shows a hybrid continous/discrete nature, it is often taught along with other discrete math disciplines. The theory behind linear programming involves basic linear algebra techniques. While appearing simple, the methods explained in class apply to a wide collection of complex real world problems. Some of them require integer and binary variables and are among the most interesting.

In summary, throughout this course in discrete mathematics, a variety of examples and applications will be explained, where by means of relatively simple tools and a clever approach,  we get to solve interesting and difficult problems. Moreover, by their work on problem sets, students will be able to practice the first step in the process of mathematical modeling, namely, understanding a problem and finding a suitable mathematical formulation that leads to the solution.