Go back to the main page

Table of contents

• Discrete Mathematics
  • Professor(s)
  • Topics covered
  • Assessment
  • Module specification
  • Past exams
  • Syllabus
  • Resources
    • Additional reading
    • Complementary learning
    • Essential reading
      • Solutions to problems in the textbook Discrete Mathematics and its Applications
    • Examples of past and current written exams
    • Kinks to be aware of
    • Mathematical symbols
    • Notes
    • On REPL
    • Supplementary videos
    • Weekly readings

---

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

• Module specification (September 2020)

Past exams

See past exams here.

Syllabus

• Syllabus PDF (September 2020)

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 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.”

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.”

• Weekly Readings and Exercises for Kenneth, H, Rosen. Discrete Mathematics and its Applications. (2012) 7th Global Edition.

Solutions to problems in the textbook Discrete Mathematics and its Applications

• 7th Edition (2012) - written explanations on Slader.com
• 8th Edition (2018) - step-by-step 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

• List of reported errors and bugs with the module.

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

• Visit this page of world-class/notes.

On REPL

• Websites

  • 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.

• YouTube

  • 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

Supplementary videos

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	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)

Weekly readings

• Reading by weeks and topics PDF