Table of contents
 Discrete Mathematics
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.
Professor(s)
 Dr. Lahcen Ouarbya
 Dr. Abdelkrim Alfalah
Topics covered
See this fabulous mind map for more details.
 Sets
 Boolean Algebra
 Propositional Logic
 Predicate Logic
 Functions
 Recursion and Mathematical Induction
 Relations
 Graphs
 Trees
 Counting
Assessment
One two hour unseen written examination and coursework (Type I)
Module specification
Past exams
Syllabus
Resources
Additional reading
 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.
Complementary learning
 Saylor Academy  “Explore the realworld 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.”
Essential reading
“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.”
Solutions to problems in the textbook Discrete Mathematics and its Applications
 7th Edition (2012)  written explanations on Slader.com
 8th Edition (2018)  stepbystep solutions in videos on Numerade.com
Examples of past and current written exams
 2014, 2015, 2016, 2017, 2018 (PDF with answers), 2020 (PDF with answers): Visit this page.
 DM March 2020 exam
Kinks to be aware of
Mathematical symbols
 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.
Notes
On REPL


Algorithms
 HopcroftKarp algorithm  Bipartite Matching  Interactive: “Here we demonstrate the HopcroftKarp 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
 BreadthFirst Search (BFS) algorithm  MIT OpenCourseWare
 DepthFirst 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
 HopcroftKarp 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 1415 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
Supplementary videos
Weeks in the module  Resource 

1 & 2 Sets  TheTrevTutor DM Video 19 
3 & 4 Functions  TheTrevTutor DM Video 5156 
5 & 6 Propositional logic  Logic in Philosophy and Mathematics 
7 & 8 Predicate logic  Logic in Philosophy and Mathematics 
9 & 10 Boolean Algebra  Karnaugh maps  (watch 4.2.1  4.2.5) 
11 & 12 Induction and recursion   TrevTutor  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) 