Mathematical Thinking in Computer Science
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?
Buy Now AED 274.99 + VAT
Monthly Subscription Starting at AED 99 + VAT
- Level Foundation
- Duration 42 hours
- Course by University of California San Diego
-
Offered by
About
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 try-this-before-we-explain-everything 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.Modules
Welcome!
-
1
Videos
-
3
Readings
1
Videos
- Promo Video
3
Readings
- Companion e-book
- Active Learning
- Python Programming Language
Why Proofs?
-
4
Videos
-
1
Readings
-
2
Assignment
2
Assignment
- Puzzle: Tile a Chessboard
- Tiles, dominos, black and white, even and odd
4
Videos
- Proofs?
- Proof by Example
- Impossibility Proof
- Impossibility Proof, II and Conclusion
1
Readings
- Slides
Existence Proofs
-
5
Videos
-
1
Readings
-
2
Assignment
2
Assignment
- Puzzle: Two Congruent Parts
- Puzzle: Splitting
5
Videos
- One Example is Enough
- Splitting an Octagon
- Making Fun in Real Life: Tensegrities (Optional)
- Know Your Rights
- Nobody Can Win All The Time: Nonexisting Examples
1
Readings
- Slides
Acknowledgements (Optional)
-
1
Readings
1
Readings
- Acknowledgements
How to Find an Example
-
6
Videos
-
1
Readings
-
4
Assignment
4
Assignment
- Puzzle: Magic Square 3 times 3
- Puzzle: Different People Have Different Coins
- Puzzle: Free Accomodation
- Is there...
6
Videos
- Magic Squares
- Narrowing the Search
- Multiplicative Magic Squares
- More Puzzles
- Integer Linear Combinations
- Paths In a Graph
1
Readings
- Slides
Optimality
-
6
Videos
-
1
Readings
-
6
Assignment
6
Assignment
- Maximum Number of Two-digit Integers
- Maximum Number of Rooks on a Chessboard
- Maximum Number of Knights on a Chessboard
- Maximum Number of Bishops on a Chessboard
- Subset without x and 2x
- Puzzle: Maximum Number of Two Digit Integers
6
Videos
- Warm-up
- Subset without x and 100-x
- Rooks on a Chessboard
- Knights on a Chessboard
- Bishops on a Chessboard
- Subset without x and 2x
1
Readings
- Slides
Computer Search
-
4
Videos
-
4
Readings
-
3
Assignment
3
Assignment
- Puzzle: N Queens
- Puzzle: 16 Diagonals
- Number of Solutions for the 8 Queens Puzzle
4
Videos
- N Queens: Brute Force Search
- N Queens: Backtracking: Example
- N Queens: Backtracking: Code
- 16 Diagonals
4
Readings
- N Queens: Brute Force Solution Code
- N Queens: Backtracking Solution Code
- 16 Diagonals: Code
- Slides
Recursion
-
3
Videos
-
2
Readings
-
7
Assignment
7
Assignment
- Largest Amount that Cannot Be Paid with 5- and 7-Coins
- Pay Any Large Amount with 5- and 7-Coins (Optional)
- Puzzle: Hanoi Towers
- Puzzle: Two Cells of Opposite Colors
- Two Cells of Opposite Colors: Feedback
- Puzzle: Guess a Number
- Puzzle: Local Maximum (Optional)
3
Videos
- Recursion
- Coin Problem
- Hanoi Towers
2
Readings
- Two Cells of Opposite Colors: Hints
- Slides
Induction
-
11
Readings
-
1
Lab
-
2
Assignment
2
Assignment
- Puzzle: Connect Points
- Induction
1
Labs
- Bernoulli's Inequality
11
Readings
- Why Induction?
- What is Induction?
- Arithmetic Series
- Plane Coloring
- Compound Interest
- Inequality Between Arithmetic and Geometric Mean
- More Induction Examples
- Where to Start Induction?
- Triangular Piece
- Proving Stronger Statements May Be Easier!
- What Can Go Wrong with Induction?
Examples, Counterexamples, Logic
-
4
Readings
-
2
Assignment
2
Assignment
- Puzzle: Always Prime?
- Examples, Counterexamples and Logic
4
Readings
- Intro
- Examples and Counterexamples
- Logic
- Summary
Reductio ad absurdum
-
6
Readings
-
8
Assignment
8
Assignment
- Girls, Boys, and Two Languages
- Puzzle: Balls in Boxes
- Puzzle: Numbers in Boxes
- Puzzle: Numbers on the Chessboard
- Numbers in Boxes
- How to Pick Socks
- Pigeonhole Principle
- Puzzle: An (-1,0,1) Antimagic Square
6
Readings
- Reductio ad Absurdum
- Balls in Boxes
- Numbers in Tables
- Pigeonhole Principle
- An (-1,0,1) Antimagic Square
- Handshakes
Double Counting
-
2
Readings
-
5
Assignment
5
Assignment
- Puzzle: Sums of Rows and Columns
- 'Homework Assignment' Problem
- 'Homework Assignment' Problem 2
- Girls and Boys
- Chess Tournaments
2
Readings
- Double Counting
- `Homework Assignment' Problem
Invariants
-
3
Readings
-
4
Assignment
4
Assignment
- Coffee with Milk
- More Coffee
- Debugging Problem
- Merging Bank Accounts
3
Readings
- Coffee with Milk
- More Coffee
- Debugging Problem
Termination
-
2
Readings
-
2
Assignment
2
Assignment
- Football Fans
- Puzzle: Arthur's Books
2
Readings
- Termination
- Arthur’s Books
Even and Odd Numbers
-
4
Readings
-
5
Assignment
5
Assignment
- Puzzle: Piece on a Chessboard
- Operations on Even and Odd Numbers
- Puzzle: Summing Up Digits
- Puzzle: Switching Signs
- Recolouring Chessboard
4
Readings
- Even and Odd Numbers
- Summing up Digits
- Switching Signs
- Advanced Signs Switching
When and Why a Solution Does Not Exist
-
6
Videos
-
2
Readings
-
3
Assignment
3
Assignment
- Puzzle: 15
- Transpositions and Permutations
- Neighbor transpositions
6
Videos
- The Rules of 15-Puzzle
- Permutations
- Proof: The Difficult Part
- Mission Impossible
- Classify a Permutation as Even/Odd
- Bonus Track: Fast Classification
2
Readings
- Reading
- Slides
The Project: Programming 15-puzzle
-
2
Videos
-
2
Readings
-
2
Assignment
2
Assignment
- Is a permutation even?
- Bonus Track: Algorithm for 15-Puzzle
2
Videos
- Project: The Task
- Quiz Hint: Why Every Even Permutation Is Solvable
2
Readings
- Even permutations
- Bonus Track: Finding The Sequence of Moves
Auto Summary
Dive into "Mathematical Thinking in Computer Science" to master essential discrete mathematics tools like induction, recursion, and logic. Ideal for those with basic math and programming knowledge, this Coursera course features interactive puzzles to deepen your understanding. Perfect for aspiring IT and computer science professionals, it offers flexible subscription options and is taught at a foundational level over 2520 minutes.
Alexander S. Kulikov
Michael Levin
Владимир Подольский