Introduction to Discrete Mathematics for Computer Science
University of California, San Diego via Coursera Specialization

61

 Write review
Overview
Class Central Tips
Discrete Mathematics is the language of Computer Science. One needs to be fluent in it to work in many fields including data science, machine learning, and software engineering (it is not a coincidence that math puzzles are often used for interviews). We introduce you to this language through a fun trythisbeforeweexplaineverything approach: first you solve many interactive puzzles that are carefully designed specifically for this online specialization, and then we explain how to solve the puzzles, and introduce important ideas along the way. We believe that this way, you will get a deeper understanding and will better appreciate the beauty of the underlying ideas (not to mention the self confidence that you gain if you invent these ideas on your own!). To bring your experience closer to ITapplications, we incorporate programming examples, problems, and projects in the specialization.
Syllabus
Course 1: Mathematical Thinking in Computer Science
 Offered by University of California San Diego. Mathematical thinking is crucial in all areas of computer science: algorithms, ... Enroll for free.
Course 2: Combinatorics and Probability
 Offered by University of California San Diego. Counting is one of the basic mathematically related tasks we encounter on a day to day basis. ... Enroll for free.
Course 3: Introduction to Graph Theory
 Offered by University of California San Diego. We invite you to a fascinating journey into Graph Theory — an area which connects the ... Enroll for free.
Course 4: Number Theory and Cryptography
 Offered by University of California San Diego. A prominent expert in the number theory Godfrey Hardy described it in the beginning of 20th ... Enroll for free.
Course 5: Delivery Problem
 Offered by University of California San Diego. In this online course we’ll implement (in Python) together efficient programs for a problem ... Enroll for free.
 Offered by University of California San Diego. Mathematical thinking is crucial in all areas of computer science: algorithms, ... Enroll for free.
Course 2: Combinatorics and Probability
 Offered by University of California San Diego. Counting is one of the basic mathematically related tasks we encounter on a day to day basis. ... Enroll for free.
Course 3: Introduction to Graph Theory
 Offered by University of California San Diego. We invite you to a fascinating journey into Graph Theory — an area which connects the ... Enroll for free.
Course 4: Number Theory and Cryptography
 Offered by University of California San Diego. A prominent expert in the number theory Godfrey Hardy described it in the beginning of 20th ... Enroll for free.
Course 5: Delivery Problem
 Offered by University of California San Diego. In this online course we’ll implement (in Python) together efficient programs for a problem ... Enroll for free.
Courses

Counting is one of the basic mathematically related tasks we encounter on a day to day basis. The main question here is the following. If we need to count something, can we do anything better than just counting all objects one by one? Do we need to create a list of all phone numbers to ensure that there are enough phone numbers for everyone? Is there a way to tell that our algorithm will run in a reasonable time before implementing and actually running it? All these questions are addressed by a mathematical field called Combinatorics. In this online course we discuss most standard combinatorial settings that can help to answer questions of this type. We will especially concentrate on developing the ability to distinguish these settings in real life and algorithmic problems. This will help the learner to actually implement new knowledge. Apart from that we will discuss recursive technique for counting that is important for algorithmic implementations. One of the main ‘consumers’ of Combinatorics is Probability Theory. This area is connected with numerous sides of life, on one hand being an important concept in everyday life and on the other hand being an indispensable tool in such modern and important fields as Statistics and Machine Learning. In this course we will concentrate on providing the working knowledge of basics of probability and a good intuition in this area. The practice shows that such an intuition is not easy to develop. In the end of the course we will create a program that successfully plays a tricky and very counterintuitive dice game. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

A prominent expert in the number theory Godfrey Hardy described it in the beginning of 20th century as one of the most obviously useless branches of Pure Mathematics”. Just 30 years after his death, an algorithm for encryption of secret messages was developed using achievements of number theory. It was called RSA after the names of its authors, and its implementation is probably the most frequently used computer program in the world nowadays. Without it, nobody would be able to make secure payments over the internet, or even log in securely to email and other personal services. In this course we will start with the basics of the number theory and get to cryptographic protocols based on it. By the end, you will be able to apply the basics of the number theory to encrypt and decrypt messages, and to break the code if one applies RSA carelessly. You will even pass a cryptographic quest! As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.

In this online course we’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important open question in Computer Science. Still, we’ll implement several solutions for real world instances of the travelling salesman problem. While designing these solutions, we will rely heavily on the material learned in the courses of the specialization: proof techniques, combinatorics, probability, graph theory. We’ll see several examples of using discrete mathematics ideas to get more and more efficient solutions.

Mathematical thinking is crucial in all areas of computer science: algorithms, bioinformatics, computer graphics, data science, machine learning, etc. In this course, we will learn the most important tools used in discrete mathematics: induction, recursion, logic, invariants, examples, optimality. We will use these tools to answer typical programming questions like: How can we be certain a solution exists? Am I sure my program computes the optimal answer? Do each of these objects meet the given requirements? In the online course, we use a trythisbeforeweexplaineverything approach: you will be solving many interactive (and mobile friendly) puzzles that were carefully designed to allow you to invent many of the important ideas and concepts yourself. Prerequisites: 1. We assume only basic math (e.g., we expect you to know what is a square or how to add fractions), common sense and curiosity. 2. Basic programming knowledge is necessary as some quizzes require programming in Python.

We invite you to a fascinating journey into Graph Theory — an area which connects the elegance of painting and the rigor of mathematics; is simple, but not unsophisticated. Graph Theory gives us, both an easy way to pictorially represent many major mathematical results, and insights into the deep theories behind them. In this online course, among other intriguing applications, we will see how GPS systems find shortest routes, how engineers design integrated circuits, how biologists assemble genomes, why a political map can always be colored using a few colors. We will study Ramsey Theory which proves that in a large system, complete disorder is impossible! By the end of the course, we will implement an algorithm which finds an optimal assignment of students to schools. This algorithm, developed by David Gale and Lloyd S. Shapley, was later recognized by the conferral of Nobel Prize in Economics. As prerequisites we assume only basic math (e.g., we expect you to know what is a square or how to add fractions), basic programming in python (functions, loops, recursion), common sense and curiosity. Our intended audience are all people that work or plan to work in IT, starting from motivated high school students.
Taught by
Alexander S. Kulikov, Michael Levin and Vladimir Podolskii