Undergraduate Programme and Module Handbook 2013-2014 (archived)
Module MATH1031: DISCRETE MATHEMATICS
Department: Mathematical Sciences
MATH1031:
DISCRETE MATHEMATICS
Type |
Open |
Level |
1 |
Credits |
20 |
Availability |
Available in 2013/14 |
Module Cap |
None. |
Location |
Durham
|
Prerequisites
- Normally, A level Mathematics at grade C or better, or
equivalent.
Corequisites
Excluded Combination of Modules
- Foundation Mathematics (MATH1641) may not be taken with or
after this module.
Aims
- To provide students with a range of tools for counting discrete
mathematical objects.
- To provide experience of a range of techniques and algorithms in
the context of Graph Theory, many with every day applications.
Content
- Principles of Counting: mathematical induction,
permutations and combinations, combinatorial vs arithmetical
proof.
- Pigeonhole principle, inclusion and
exclusion.
- Prime numbers: density of prime numbers, modular
arithmetic, public key encryption.
- Generating Functions: partitions, recurrence
relations.
- Special Numbers: Fibonacci, Fermat, Mersenne, Stirling
etc.
- Algorithms and Finite State Machines: elementary
discussion of algorithmic complexity.
- Graphs: basic concepts, Euler paths, maze algorithms,
random walks on graphs, Euler's theorem, planar graphs, brief
introduction to colouring graphs, the Six and Five Colour
Theorems.
- Optimisation Algorithms on Graphs: trees (relevant to
searching data structures, genetics, decision problems), shortest and
longest paths, flow problems, matching/assignment problems, latin
squares, travelling salesman and Chinese postman
problems.
Learning Outcomes
- By the end of the module students will: be able to solve a
range of predictable and less predictable problems in Discrete
Mathematics.
- have an awareness of the basic concepts of theoretical
mathematics in the field of Discrete Mathematics.
- have a broad knowledge and basic understanding of these
subjects demonstrated through one or more of the following topic
areas: Principles of counting.
- Recurrence relations and generating functions.
- Algorithms and finite state machines.
- Graphs.
- Algorithms on graphs.
- students will have basic mathematical skills in the following
areas: Spatial awareness, Abstract reasoning, Modelling.
- students will have basic problem solving skills.
Modes of Teaching, Learning and Assessment and how these contribute to
the learning outcomes of the module
- Lectures demonstrate what is required to be learned and the
application of the theory to practical examples.
- Tutorials provide the practice and support in applying the
methods to relevant situations as well as active engagement and feedback
to the learning process.
- Summative weekly coursework provides an incentive for students
to consolidate the learning of material as the module progresses (there
are no higher level modules in the department of Mathematical Sciences
which build on this module). It serves as a guide in the correct
development of students' knowledge and skills, as well as an aid in
developing their awareness of standards required.
- The end-of-year written examination provides a substantial
complementary assessment of the achievement of the student.
Teaching Methods and Learning Hours
Activity |
Number |
Frequency |
Duration |
Total/Hours |
|
Lectures |
42 |
2 per week |
1 Hour |
42 |
|
Tutorials |
19 |
Weekly in weeks 2-10, 12-21. |
1 Hour |
19 |
■ |
Preparation and Reading |
|
|
|
139 |
|
Total |
|
|
|
200 |
|
Summative Assessment
Component: Examination |
Component Weighting: 90% |
Element |
Length / duration |
Element Weighting |
Resit Opportunity |
Written examination |
3 hours |
100% |
Yes |
Component: Coursework |
Component Weighting: 10% |
Element |
Length / duration |
Element Weighting |
Resit Opportunity |
One written assignment each teaching week |
|
100% |
Completing the May/June examination paper in the
summer, to be returned by the start of the resit exam
period |
45 minute collection paper in the first week of
Epiphany term.
■ Attendance at all activities marked with this symbol will be monitored. Students who fail to attend these activities, or to complete the summative or formative assessment specified above, will be subject to the procedures defined in the University's General Regulation V, and may be required to leave the University