The module introduces fundamental concepts in the area of discrete mathematics
The focus of the module is on central mathematical concepts in discrete mathematics and on applications of discrete mathematics to algorithms and data structures. The module teaches mathematical and algorithmic tools, and prepares students for later, more specialized modules in their degree, offered by the Computer Science department and Warwick's Mathematics Institute. A particular emphasis is to demonstrate students how discrete mathematics can be used in modern computer science, with a particular focus on algorithmic applications.
This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.
Counting: inclusion/exclusion, binomial coefficients and Pascal's triangle, the twelvefold way (combinations, permutations, etc.), fundamental counting sequences (Catalan, Fibonacci, etc.), combinatorial proofs ("Proofs that really count")
Elementary number theory: floors and ceilings, modular arithmetic, GCD and Euclid's algorithm, diophantine equations, Chinese remainder theorem
Partially ordered sets: posets and Hasse diagrams, chains and antichains (Dilworth, Sperner), lattices, linear extensions and topological sorting
Graph theory basics: basics, degree sequences, paths and cycles, trees, bipartite graphs, Euler tours
Asymptotic notation: Big-O, little-o, Big-Omega, little-omega, Theta etc., Master theorem
Recurrence relations: characteristic polynomials, generating functions
By the end of the module, students should be able to:
Reading lists can be found in Talis
Acquiring fundamental knowledge, skills and tools in the area of discrete mathematics, including familiarity with the concepts of mathematical rigour and formal proof.
Critical thinking and creativity, problem solving skills, endurance and persistence
| Type | Required |
|---|---|
| Lectures | 30 sessions of 1 hour (30%) |
| Seminars | 9 sessions of 1 hour (9%) |
| Private study | 61 hours (61%) |
| Total | 100 hours |
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Students can register for this module without taking any assessment.
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| Problem sheet 1 | 4% | Yes (waive) | |
|
Each problem sheet is marked out of 10 and the overall coursework mark is calculated as the average of the five marked assignments. |
|||
| Problem sheet 2 | 4% | Yes (waive) | |
|
Each problem sheet is marked out of 10 and the overall coursework mark is calculated as the average of the five marked assignments. |
|||
| Problem sheet 3 | 4% | Yes (waive) | |
|
Each problem sheet is marked out of 10 and the overall coursework mark is calculated as the average of the five marked assignments. |
|||
| Problem sheet 4 | 4% | Yes (waive) | |
|
Each problem sheet is marked out of 10 and the overall coursework mark is calculated as the average of the five marked assignments. |
|||
| Problem sheet 5 | 4% | Yes (waive) | |
|
Each problem sheet is marked out of 10 and the overall coursework mark is calculated as the average of the five marked assignments. |
|||
| Centrally-timetabled examination (On-campus) | 80% | No | |
|
In-person written examination (closed book)
|
|||
| Weighting | Study time | Eligible for self-certification | |
|---|---|---|---|
| In-person examination - resit | 100% | No | |
|
In-person written examination - resit (closed book)
|
|||
Feedback on problem sets in seminars.
If you take this module, you cannot also take:
This module is Core for: