Module 18189.2 (2004)
Syllabus page 2004/2005
06-18189
Mathematics for Computer Science
Level 1/C
Achim Jung
Achim Jung (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.)
Changes and updates
New module for 2004/05 (in part replaces Maths and Logic A & B). Examination length increased to 3 hrs after discussion with students.
Relevant Links
Outline
The module provides an introduction to mathematical concepts relevant to computer science. Discrete mathematics: numbers and arithmetic; elementary set theory, relations and functions; proofs and mathematical induction; elementary counting principles; binomial theorem; graphs and trees. Linear algebra: concepts, structures and methods, placing special emphasis on their application in modelling and solving computational problems.
Aims
The aims of this module are to:
- introduce the basic discrete mathematics concepts that have applications in computer science
- introduce the core concepts and fundamental algorithms of linear algebra
- illustrate how linear algebra concepts and algorithms help in solving computational problems
Learning Outcomes
| On successful completion of this module, the student should be able to: | Assessed by: | |
| 1 | apply basic set theory | Continuous assessment, examination |
| 2 | apply the concept of equivalence relations and theorems about them | Continuous assessment, examination |
| 3 | apply the principle of mathematical induction | Continuous assessment, examination |
| 4 | perform combinatorial enumeration and use binomial coefficients and factorial notation | Continuous assessment, examination |
| 5 | apply the concept of a combinatorial graph and tree | Continuous assessment, examination |
| 6 | apply linear algebra algorithms on paper to small problem instances | Continuous assessment, examination |
| 7 | explain how these algorithms can be implemented, recognizing numerical stability issues | Continuous assessment, examination |
| 8 | identify and explain the structural and conceptual elements of linear algebra in computational settings | Continuous assessment, examination |
| 9 | apply linear algebra as a modelling language and as a solution technique for computational problems | Continuous assessment, examination |
Restrictions, Prerequisites and Corequisites
Restrictions:
None
Prerequisites:
None
Co-requisites:
None
Teaching
Teaching Methods:
2 hrs lectures, 1 hr tutorial/exercise class per week
Contact Hours:
Assessment
- Supplementary (where allowed): As the sessional assessment
- 3 hr examination (80%), continuous assessment (20%). Resit by examination only with the continuous assessment mark carried forward.
Recommended Books
| Title | Author(s) | Publisher, Date |
| Discrete Mathematics | S. Lipschuts & M. Lipson | Schaum Outline Series, |
Detailed Syllabus
-
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
- Numbers and arithmetic (~3 hours)
- What are real numbers and how are they represented?
- Fractions and decimals
- Rationals and irrationals
- Elementary algebra (revision)
- Number systems
- Review of natural numbers, integers, rationals, and the reals
- Computing modulo a number
- Complex numbers
- Systems of linear equations
- Gaussian elimination
- Underspecified equation systems
- Overspecified equation systems
- Analytic geometry
- Representing lines and planes, intersection
- Orthogonality and projection
- Bases in the plane and in three-dimensional space
- Linear transformations and matrices
- Types of linear transformations
- Description of linear transformations with matrices
- Matrix algebra
- Base changes
- Vector spaces
- General definition and examples
- Linear and affine subspaces
- Orthogonalisation
- Determinants
- Determinants
- Eigenvalues and eigenvectors
- Diagonalisation
Last updated: 8 Apr 2005
Source file: /internal/modules/COMSCI/2004/xml/18189.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus