Module 18189.2 (2005)
Syllabus page 2005/2006
06-18189
Mathematics for Computer Science
Level 1/C
Unknown/Left
Unknown/Left
Uday Reddy (coordinator)
Unknown/Left
Uday Reddy (coordinator)
10+10 credits in Semester 1 and Semester 2
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
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 | identify and explain the structural and conceptual elements of linear algebra in computational settings | Continuous assessment, examination |
| 8 | 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. Lipschutz & M. Lipson | Schaum Outline Series, |
| Elementary Linear Algebra | Stanley I Grossman | Saunders College Publishing, 1991 |
| Linear Algebra for Engineers and Scientists | Kenneth Hardy | Pearson Education International, 2005 |
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
- Geometry of the plane
- Lengths and angles
- Cartesian and polar coordinates
- Rotation, translation, and scaling
- The field of complex numbers
- Analytic Geometry in three dimensions
- Euclidian distance
- Linear combination of position vectors
- Lines and planes
- Orthogonality, angles, and inner product
- Projection and reflection
- Systems of linear equations
- Gaussian elimination
- Homogeneous systems
- Under-specified equation systems
- Matrices and matrix algebra
- Addition and scaling
- Matrix multiplication
- Transposition
- Row operations
- Inversion and invertibility
- Fields and vector spaces
- Fields
- Key examples: Q, R, C, and F2
- Vector spaces
- Key examples: straight-line movements and tuples
- Linear subspaces
- Generating sets and bases
- Dimension
- Subspaces by equations
- Affine subspaces
- Linear Transformations
- The main types: Scaling, rotation, reflection, translation, shear, projection
- Describing transformations by matrices
- Transformations and systems of linear equations
- Coordinate change
- Orthonormal bases
- Homogeneous coordinates
Last updated: 18 Nov 2005
Source file: /internal/modules/COMSCI/2005/xml/18189.xml
Links | Outline | Aims | Outcomes | Prerequisites | Teaching | Assessment | Books | Detailed Syllabus