- Discrete Mathematics
This module helps hone your skills in thinking abstractly. It also introduces you to many of the discrete models used to help understand and design computational systems. Through this module, you'll develop the fundamental discrete mathematical tools that will support you during the BSc degree. Particular attention is paid to notions of experimentation, reasoning and generalisation.
- Dr. Lahcen Ouarbya
- Dr. Abdelkrim Alfalah
See this fabulous mind map for more details.
- Sets
- Boolean Algebra
- Propositional Logic
- Predicate Logic
- Functions
- Recursion and Mathematical Induction
- Relations
- Graphs
- Trees
- Counting
One two hour unseen written examination and coursework (Type I)
- ⭐ 🥉 Mathematics for Computer Science - "Proofs, Structures, Counting, Probability, Recurrences."
- A Guide to Writing Proofs.
- Book of Proof - "Fundamentals, How to Prove Conditional Statements, More on Proof, Relations, Functions and Cardinality."
- Common Mistakes in Discrete Math (from the companion website to the essential reading for the book Discrete Mathematics and its Applications).
- Discrete Mathematics Questions and Answers - "Our 1000+ Discrete Mathematics questions and answers focuses on all areas of Discrete Mathematics subject covering 100+ topics in Discrete Mathematics."
- Induction: going through examples (UoL students).
- Lectures in discrete mathematics - "Arithmetic, Logic and Numbers, Sets, Equivalence and Order, Lists, Decisions and Graphs."
- Matching (Graph Theory) - "Definition, terminology, bipartite matching, examples."
- Readings from MIT OpenCourseWare on proofs, graph theory, recurrences, probability.
- Set Theory for Computer Science.
- Solving Linear Recurrence Relations - From University of California, Berkeley, from this page.
- Saylor Academy - "Explore the real-world applications of mathematics through algebra, calculus, statistics, and geometry. You can earn a free certificate of completion for any of these online Mathematics courses, or use many of them to earn credit in leading college programs."
"The essentials readings for this course will come from the following text book, which is available in the University of London digital library:
- Kenneth, H, Rosen. Discrete Mathematics and its Applications. (2012) 7th Global Edition
- David Mackinson, Sets, Logic and Maths for Computing, Springer Verlag. 2012
This course does not require you to read the whole book, you will be given specific readings for each topic from these texts are listed with direct links on the Readings page for each topic. You will also be asked to do some independent research from online sources or using the University of London digital library."
- 7th Edition (2012) - written explanations on Slader.com
- 8th Edition (2018) - step-by-step solutions in videos on Numerade.com
- 2014, 2015, 2016, 2017, 2018 (PDF with answers), 2020 (PDF with answers): Visit this page.
- DM March 2020 exam
- The list of mathematical symbols on Wikipedia is a handy reference. Chapter 1 of Kenneth, H, Rosen. Discrete Mathematics and its Applications. (2012) 7th Edition is outside the scope of the essential readings for this module, but provides a solid foundation to understand the notations and some proof techniques used during the course.
- Type mathematical symbols (online keyboard) - Online keyboard to help with typing mathematical symbols.
-
- Algorithms
- Hopcroft-Karp algorithm - Bipartite Matching - Interactive: "Here we demonstrate the Hopcroft-Karp algorithm that solves the problem of finding maximal matchings on bipartite graphs."
- VisuAlgo - Visualising data structures and algorithms through animation.
- Binomial theorem
- Intro to the Binomial Theorem - Khan Academy
- Graph theory
- D3 Graph Theory - "Learn graph theory interactively."
- Matching (Graph Theory) - "Definition, terminology, bipartite matching, examples."
- Rules of inference - logic proofs
- Rules of Inference and Logic Proofs - Covers modus ponens, modus tollens, disjunctive syllogism, De Morgan's law, biconditional, conjunctions, disjunctions, equivalences, double negation.
- Algorithms
-
- Algorithms
- Algorithms: Graph Search, DFS and BFS - HackerRank
- Breadth-First Search (BFS) algorithm - MIT OpenCourseWare
- Depth-First Search (DFS), Topological Sort - MIT OpenCourseWare
- Graph Traversals - BFS & DFS -Breadth First Search and Depth First Search - Abdul Bari
- Maximum Matching Algorithm - HEGARTYMATHS
- Dijkstra's algorithm
- Dijkstra's Shortest Path Algorithm - Graph Theory - WilliamFiset
- Graph Data Structure 4. Dijkstra’s Shortest Path Algorithm - Computer Science
- Dijkstra's algorithm in 3 minutes — Review and example - Michael Sambol
- Hopcroft–Karp algorithm
- Hopcroft karp Algorithm explanation - Holly Baker
- Hopcroft-Karp Algorithm - Samuel Russell
- Hopcroft–Karp algorithm - Joromy Bou Khalil
- Kruskal’s algorithm
- Kruskal's algorithm in 2 minutes — Review and example - Michael Sambol
- Kruskal’s Algorithm for Minimum Spanning Tree - GeeksforGeeks
- Prim's algorithm
- Prim's algorithm in 2 minutes — Review and example - Michael Sambol
- Computer Sc - Discrete Mathematical Structures (playlist) - Kamala Krithivasan
- Discrete Math 1: Sets, propositional logic, factorials, permutations, combinations, proofs, mathematical induction, injective/surjective/bijective functions, inverse functions, algorithms (playlist) - TheTrevTutor
- Discrete Math 2: Permutations, combinations, probability, graph theory, trees, Dijkstra's Algorithm (playlist) - TheTrevTutor
- Discrete Math I (playlist) - Kimberly Brehm
- Discrete mathematics (playlist) - GATEBOOK Video Lectures
- Recurrence relations: see lectures 14-15 of Mathematics for Computer Science (2010) (playlist) - MIT OpenCourseWare
- Sets, sequences, functions, summations, matrices, algorithms (playlist) - Kimberly Brehm
- Strong Induction Examples - Michael Barrus
- The Karnaugh Map - Rules of Simplification - Jonnie Palmer
- Transitive closure - GVSUmath
- Algorithms
| Weeks in the module | Resource |
|---|---|
| 1 & 2 Sets | TheTrevTutor DM Video 1-9 |
| 3 & 4 Functions | TheTrevTutor DM Video 51-56 |
| 5 & 6 Propositional logic | Introduction to mathematical thinking (0.0 - 4.3) |
| 7 & 8 Predicate logic | Introduction to mathematical thinking (5.1 - 6.4) |
| 9 & 10 Boolean Algebra | Karnaugh maps - (watch 4.2.1 - 4.2.5) |
| 11 & 12 Induction and recursion | _ Introduction to mathematical thinking (7.1 - 8.4) _ Math for CS - MIT (Lecture 1, 2, 3, 14 and 15 and reading from MCS notes) |
| 13 & 14 Graphs | _ Math for CS - MIT (Lecture 6 to 10 and reading from MCS notes) _ FreeCodeCamp - Algorithms Course - Graph Theory Tutorial from a Google Engineer (focuses more on implementation than theory) |
| 15 & 16 Trees | Partly covered in Math for CS - MIT videos for 13/14. |
| 17 & 18 Relations | Math for CS - MIT (Lecture 11 and reading from MCS notes) |
| 19 & 20 Combinatorics | Math for CS - MIT (Lecture 16 and 17 and reading from MCS notes) |