Data ScienceDiscover Coursera Plus
Data Science · Year 2 · Theoretical computer science and statistics
S3 Discrete mathematics and algorithms
Learn to prove, count and reason about graphs, then design and analyze efficient algorithms.
173hours of coursework
18weeks at 10 h
2steps
9new courses
2universities
Target skills
- Proof by induction, by contradiction, invariants
- Combinatorics, discrete probability, graph theory
- Modular arithmetic and RSA cryptography
- Divide and conquer, graphs, greedy algorithms, dynamic programming, NP-completeness
Semester project
The UCSD Delivery Problem project: solve a travelling salesman problem and compare heuristics.
Courses this semester
- 1University of California San DiegoBeginnerPython
Stated prerequisites: Basic math (fractions, squares), basic Python (functions, loops, recursion)
Show the 5 courses
Course Level Length Rating (reviews) Mathematical Thinking in Computer Science Beginner 42 h 4.4 (2,289) Combinatorics and Probability Beginner 23 h 4.6 (874) Introduction to Graph Theory Beginner 21 h 4.5 (1,073) Number Theory and Cryptography Beginner 17 h 4.5 (610) Delivery Problem Beginner 13 h 4.7 (376) - 2Stanford University (Stanford Online)IntermediateC, Java, Python
Stated prerequisites: Programming in at least one language (C, Java or Python); familiarity with proofs (induction, contradiction); discrete probability
Show the 4 courses
Course Level Length Rating (reviews) Divide and Conquer, Sorting and Searching, and Randomized Algorithms Intermediate 15 h 4.8 (5,342) Graph Search, Shortest Paths, and Data Structures Intermediate 14 h 4.8 (2,002) Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming Intermediate 15 h 4.8 (1,279) Shortest Paths Revisited, NP-Complete Problems and What To Do About Them Intermediate 13 h 4.8 (832)
Reading
Mathematics for Computer ScienceE. Lehman, F. T. Leighton, A. R. Meyer (MIT)The reference for proofs, combinatorics and graphs; covers the whole UCSD course and more.Free, CC BY-SA
AlgorithmsJeff EricksonCompanion to Stanford Algorithms: recursion, dynamic programming, graphs, reductions, with many exercises.Free, CC BY 4.0
Things to watch
- Stanford Algorithms assumes you can read proofs: take it after Discrete Mathematics.
- For more practice: Data Structures and Algorithms (UCSD, 182 h), listed in the Computer Science file.
With Coursera Plus
This semester takes 173 hours, about 4 months at 10 hours a week. A Coursera Plus subscription gives access to most of its courses during that time.