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?
Mathematical Thinking in Computer Science
This course is part of Introduction to Discrete Mathematics for Computer Science Specialization
137,513 already enrolled
(2,236 reviews)
Skills you'll gain
Details to know
Add to your LinkedIn profile
57 assignments
See how employees at top companies are mastering in-demand skills
Build your subject-matter expertise
- Learn new concepts from industry experts
- Gain a foundational understanding of a subject or tool
- Develop job-relevant skills with hands-on projects
- Earn a shareable career certificate
Earn a career certificate
Add this credential to your LinkedIn profile, resume, or CV
Share it on social media and in your performance review
There are 6 modules in this course
Why are some arguments convincing and some others are not? What makes an argument convincing? How can you establish your argument in such a way that there is no room for doubt left? How can mathematical thinking help with this? In this section, we start digging into these questions. Our goal is to learn by examples how to understand proofs, how to discover them on your own, how to explain them, and — last but not least — how to enjoy them: we will see how a small remark or a simple observation can turn a seemingly non-trivial question into an obvious one.
What's included
10 videos6 readings4 assignments
How can we be certain that an object with certain requirements exist? One way to show this, is to go through all objects and check whether at least one of them meets the requirements. However, in many cases, the search space is enormous. A computer may help, but some reasoning that narrows the search space is important both for computer search and for "bare hands" work. In this module, we will learn various techniques for showing that an object exists and that an object is optimal among all other objects. As usual, we'll practice solving many interactive puzzles. We'll show also some computer programs that help us to construct an example.
What's included
16 videos6 readings13 assignments
We'll discover two powerful methods of defining objects, proving concepts, and implementing programs — recursion and induction. These two methods are heavily used in discrete mathematics and computer science. In particular, you will see them frequently in algorithms — for analysing correctness and running time of algorithms as well as for implementing efficient solutions. For some computational problems (e.g., exploring networks), recursive solutions are the most natural ones. The main idea of recursion and induction is to decompose a given problem into smaller problems of the same type. Being able to see such decompositions is an important skill both in mathematics and in programming. We'll hone this skill by solving various problems together.
What's included
3 videos13 readings9 assignments1 ungraded lab
Mathematical logic plays a crucial and indispensable role in creating convincing arguments. We use the rules and language of mathematical logic while writing code, while reasoning and making decisions, and while using computer programs. This week we’ll learn the basics of mathematical logic, and we'll practice tricky and seemingly counterintuitive, but yet logical aspects of mathematical logic. This will help us to write readable and precise code, and to formulate our thoughts rigorously and concisely.
What's included
10 readings10 assignments
"There are things that never change". Apart from being just a philosophical statement, this phrase turns out to be an important idea in discrete mathematics and computer science. A property that is preserved during a process is called an invariant. Invariants are used heavily in analyzing the behavior of algorithms, programs, and other processes. Being able to find the right invariant is an important skill that we will develop together in this module.
What's included
11 readings16 assignments
In this module, we consider a well-known 15-puzzle where one needs to restore order among 15 square pieces in a square box. It turns out that the behavior of this puzzle is determined by mathematics: it is solvable if and only if the corresponding permutation is even. To understand what it means and why it is true, we will learn the basic properties of even and odd permutations — an important notion in algebra and discrete mathematics. Together, we will implement a number of simple methods for working with permutations. You will then use them as building blocks to implement a program that solves any configuration of this game in the blink of an eye!
What's included
8 videos4 readings5 assignments
Instructors
Offered by
Recommended if you're interested in Algorithms
Stanford University
University of Pennsylvania
University of London
University of Michigan
Why people choose Coursera for their career
Learner reviews
Showing 3 of 2236
2,236 reviews
- 5 stars
64.15%
- 4 stars
23.43%
- 3 stars
7.09%
- 2 stars
2.14%
- 1 star
3.16%
New to Algorithms? Start here.
Open new doors with Coursera Plus
Unlimited access to 7,000+ world-class courses, hands-on projects, and job-ready certificate programs - all included in your subscription
Advance your career with an online degree
Earn a degree from world-class universities - 100% online
Join over 3,400 global companies that choose Coursera for Business
Upskill your employees to excel in the digital economy
Frequently asked questions
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
When you enroll in the course, you get access to all of the courses in the Specialization, and you earn a certificate when you complete the work. Your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.
If you subscribed, you get a 7-day free trial during which you can cancel at no penalty. After that, we don’t give refunds, but you can cancel your subscription at any time. See our full refund policy.