Discrete Mathematics & Structures for CS

Updated: Feb 13, 2020

Discrete mathematics deals with objects that come in discrete bundles, e.g., 1 or 2 babies. In contrast, continuous mathematics deals with objects that vary continuously, e.g., 3.42 inches from a wall. Think of digital watches versus analog watches (ones where the second hand loops around continuously without stopping). Why study discrete mathematics in computer science? It does not directly help us write programs. At the same time, it is the mathematics underlying almost all of computer science.

Here are a few examples:

• Designing high-speed networks and message routing paths.

• Finding good algorithms for sorting.

• Performing web searches.

• Analyzing algorithms for correctness and efficiency.

• Formalizing security requirements.

• Designing cryptographic protocols.

Discrete mathematics uses a range of techniques, some of which is seldom found in its continuous counterpart. The following specific applications in computer science:

1. Sets, functions and relations

2. Proof techniques and induction

3. Number theory

a) The math behind the RSA Crypto system

4. Counting and combinatorics

5. Probability

a) Spam detection

b) Formal security

6. Logic

a) Proofs of program correctness

7. Graph theory i

a) Message Routing

b) Social networks

8. Finite automata and regular languages

a) Compilers

In the field you write precise mathematical statements that captures what we want in each application, and learn to prove things about these statements. For example, how will we formalize the infamous zero knowledge property? How do we state, in mathematical terms, that a banking protocol allows a user to prove that she knows her password, without ever revealing the password itself?

Recent Posts

See All

Dijkstra shortest path algorithm

Word ladder game (change only one letter to go from Fool to Sage): Fool, Pool, Poll, Pole, Pale, Sale, Sage. How? Dijkstra shortest path algorithm

Deep Learning for Algorithmic Trading

Finance is highly nonlinear and sometimes stock price data can even seem completely random. Machine learning and Deep Learning have found their place in the financial institutions for their power in p

Statistical Arbitrage Trading Pairs

What are z score values? A Z score is the value of a supposedly normal random variable when we subtract the mean and divide by the standard deviation, thus scaling it to the standard normal distributi

©2020 by Arturo Devesa.