Module 08762.1 (2003)
Syllabus page 2003/2004
06-08762
Mathematics & Logic A
Level 1/C
Unknown/Left
Manfred Kerber (coordinator)
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus
The Module Description is a strict subset of this Syllabus Page. (The University module description has not yet been checked against the School's.)
Relevant Links
Outline
Numbers and arithmetic; elementary set theory, relations and functions; proofs and mathematical induction; elementary counting principles; binomial theorem; graphs and trees.
Aims
The aims of this module are to:
- introduce the basic discrete mathematics concepts that have applications in computer science
Learning Outcomes
| On successful completion of this module, the student should be able to: | Assessed by: | |
| 1 | understand and apply basic set theory | Continuous assessment, examination |
| 2 | understand and apply the concept of equivalence relations and the theorems about them | Continuous assessment, examination |
| 3 | understand and apply the principle of mathematical induction | Continuous assessment, examination |
| 4 | perform combinatorial enumeration and use binomial coefficients and factorial notation | Continuous assessment, examination |
| 5 | understand and apply the concept of a combinatorial graph and tree | Continuous assessment, examination |
Restrictions, Prerequisites and Corequisites
Restrictions:
None
Prerequisites:
None
Co-requisites:
06-08764 (Mathematics & Logic B) (linked module)
Teaching
Teaching Methods:
2 lectures and 1 exercise class per week.
Contact Hours:
Assessment
- Supplementary (where allowed): As the sessional assessment
- 3 hr examination (80%), continuous assessment (20%), divided equally between this module and 06-08764 (Mathematics & Logic B). Resit by examination only.
Recommended Books
| Title | Author(s) | Publisher, Date |
| Discrete Mathematics | S. Lipschuts & M. Lipson | Schaum Outline Series, |
Detailed Syllabus
-
Numbers and arithmetic (~3 hours)
- What are real numbers and how are they represented?
- Fractions and decimals
- Rationals and irrationals
- Elementary algebra (revision)
- Sets (~5 hours)
- Set notation - including standard sets N, Z, Q, R
- Equality of sets (with proofs)
- Predicate notation: { x : P(x) }
- Subsets; union, intersection, difference, complement; algebra of sets
- Distributive laws; de Morgan laws
- Ordered pairs and triples; cartesian products
- Power set
- Sets and logic (throughout)
- Relations and functions (4-5 hours)
- Partitions and equivalence relations
- Partial order relations
- Functions; one-one, onto, bijections
- Proofs (~3 hours and throughout)
- Sequences, recurrences and induction
- Counting (4-5 hours)
- Sum rule; inclusion-exclusion
- Product rule
- Binomial coefficients and binomial theorem (positive integer exponent)
- Graphs and trees (~3 hours)
- Handshaking lemma; degree sequences
- Specific families: complete graphs, circuits, paths, complete bipartite
- Connectedness; bipartiteness
- Trees, rooted trees; links with partial orders
Last updated: 3 Nov 2003
Source file: /internal/modules/COMSCI/2003/xml/08762.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus