Discrete Structures for Computing#

This course presents an introduction to the mathematical foundations of computer science, with an emphasis on reasoning, analysis, and algorithmic thinking.

Computers are fundamentally digital machines. Everything is binary, either a 0 or a 1. This finite and discrete nature of computers links them deeply to discrete mathematics. Discrete mathematics is the study of mathematical structures that are somehow “discrete”. Discrete contrasts with “continuous”, as you know well from the real numbers \(\mathbb{R}\) and calculus. Informally, discrete structures are ones which have a relationship to the natural numbers \(0, 1, 2, \ldots\)

In this course we will study the discrete mathematical foundations of computer science. This includes not only the discrete structures themselves, like sets, functions, relations, matrices, and graphs, but also the logical and algorithmic application of them to computing.

Table of Contents#

What is Discrete?#

One of the most prototypical examples of discrete objects are the integers \(\mathbb{Z} = \{\ldots, -2, -1, 0, 1, 2, \ldots\}\). But, it is so much more.

  • The steps taken by a computer program

  • The number of different possible 10-character passwords

  • The pixels in an digital image

Unsurprisingly, the study of discrete mathematics is highly related to the study of problems which computers can solve. Some examples include:

  • How does Google maps find directions between two points?

  • How do we simulate the motion of planets, stars, and galaxies?

  • How many different games of chess can be played?

  • What possible combinations of ACGT are possible in a particular gene?

  • How can passwords, banking information, credit card information, be transported securely over the internet?

  • What is the best design for a city’s public transit network?

  • How do you search for a keyword in a document?

  • and many more…

All of this is to say that the world of discrete mathematics is vast and very often quite challenging. Fundamental questions in computer science are typically discrete and deceptively simple-looking. In fact, one application of discrete mathematics is to answer the question: “how difficult is it to solve problem X?” This is the branch of computer science known as the theory of computation. One small example of this may be seen later in Graph Theory.

Reading this Text: Goals and Tips#

Unlike previous courses you may have taken in mathematics and computer science, discrete mathematics is more about understanding and reasoning than it is about regurgitating facts. There is often not necessarily a single correct answer nor a single correct way of finding the answer. Therefore, some amount of creativity and original thought is needed on the part of the reader. This rather unstructured nature generally makes learning discrete mathematics more difficult. Here are some tips.

Tip

Carefully understand the definitions. How can you solve a problem or write a proof if you don’t know what you are being asked? Check back with the Glossary if you ever need a quick definition. Do you think something is missing from the glossary? Let me know and I’ll add it in.

Tip

Practice makes progress. Getting better at mathematical thinking requires practice. This text contains many knowledge checks, problem sets, and exercises.

Throughout this text, checkpoints should be completely immediately upon encountering them. They serve as a knowledge check to ensure you understand the content before building off it into more difficult content. A checkpoint looks like this:

Tips

This is a checkpoint. Did you read the previous tips?

Tips Solution

Please go read the tips!

There are also exercises throughout this text, mainly at the end of sections for you to test and apply your knowledge. Exercises come in three levels of difficulty: easy, hard, and challenge. Despite the name, you should feel that “challenge” exercises are still possible to solve, but may require a little more time to complete. Exercises may or may not come with solutions.

Exercise 1

This is an easy exercise.

Exercise 2

This is a hard exercise.

Exercise 3

This is a challenge exercise.

Learning Goals#

1. Mathematical Reasoning

Ability to read, understand, construct, and verify mathematical writing, arguments, and proofs.

2. Combinatorial Analysis

Techniques for counting different kinds of objects.

3. Discrete Structures

Understanding and working with abstract mathematical structures and relationships between them. Also, how to represent them on a computer.

4. Algorithmic Thinking

Solve problems via a logical and precise sequence of steps. Verify that a particular algorithm will solve a particular problem.

5. Applications

Appreciate the wide range of fields to which discrete mathematics can be applied. Sometimes creativity and ingenuity is needed to find the relation between a problem and tools from discrete mathematics to solve that problem.

#

A note to the particularly keen reader.#

Attention

Nobody is perfect. There will be typos, mistakes, and errors in these notes. If you find a typo or error, please email me. Rather than spend hours working on a problem and questioning your own sanity, please ask for help! Maybe the solution is just wrong…

Alex Brandt, abrandt5@uwo.ca