School of Electronics and Computer Science:
COMP1007 Discrete Mathematics for Computer Science
Basic Information
| School | Dept- Electronics & Computer Science |
|---|---|
| Known as | COMP1007. |
| Session and Semester | Semester One, 2011 - 2012 |
| Credit | 10 Credit Points |
| Unit Leader | Dr Pawel Sobocinski |
| Teachers | Dr. Maria Polukarov |
| Moderators | Prof RI "Bob" Damper |
| Study | 100 hours of which approximately 20-24 hours is lectures. The remaining time should be allocated to self-study and revision. |
| Assessment | Examination 70%, Class tests and take home assignments 30% |
| Coursework | 2 take home assignments, 2 tests in class, best 3 count 10% each. |
| Teaching | Lectures 24, Tutorials 12 |
| Referral | On referral, this unit will be assessed 100% by examination. |
| Syllabus Approved |
Description
Aims
- To extend the students' basic mathematical awareness and skills.
- To give the mathematical background necessary for other compulsory modules.
- To give the study skills necessary for students to learn new areas of mathematics (including those we do not cover in the degree).
- To give a range of useful problem solving skills.
- To give a feeling for the mathematical approach to the study of computer science.
Learning Outcomes
Knowledge and Understanding
Having successfully completed the module, you will be able to demonstrate knowledge and understanding of:
At the end of COMP1007, students will know and understand the basic concepts of discrete structures as they apply to computer science, and have developed an appreciation of the way that discrete mathematics can assist their own problem solving and implementation of solutions.
Intellectual Skills
Having successfully completed the module, you will be able to:
- Define the terms used in the syllabus below
- Manipulate formulae involving sets, integers, reals and functions of such quantities
- Solve simple problems involving sets, functions, graphs and trees
- Construct sound logical arguments, including use of induction
- Appreciate the importance of discrete mathematics to the understanding of computation.
Practical Skills
Having successfully completed the module, you will be able to:
COMP1007 is essentially theoretical and abstract. However, students are encouraged to use software tools such as spreadsheets, graphing packages, etc. to help concrete visualisation of the topics taught.
General Transferable (key) Skills
Having successfully completed the module, you will be able to:
Facility with mathematics is perhaps the ultimate transferrable skill for a computer scientist or engineer, promoting a logical and analytical approach to problem solving over a wide range of topics and domains, and providing a toolkit of general principles for understanding relationships between concepts and objects.
Topics Covered
- Sets, functions and relations
- Basic notation, represenations and examples. Disjoint sets. Subsets.
- Operations on sets: Union, intersection and complement.
- Pairs, tuples, cartesian products, powersets.
- Functions: injections, surjections, bijections.
- Relations. Equivalence relations and partial orders.
- Cardinality, infinite sets.
- Logic
- Propositional logic. Logical connectives. Semantics.
- Natural deduction, soundness and completeness.
- Combinatorics
- Counting with sets. Pigeonhole principle, inclusion-exclusion principle.
- Combinations, Permutations.
- Binomials.
- Introduction to discrete probability.
- Induction and Recursion
- Mathematical induction, structural induction.
- Lists, trees, recursive functions, recursive data structures.
Teaching and learning activities
Teaching methods include
Teaching methods are traditional and lecture based, as appropriate for the study of foundational mathematics.
Learning activities include
Active engagement with frequent practice on examples is the only way to learn mathematics. Such engagement is strongly encouraged through regular courseworks and class tests, which count towards the unit assessment.
Feedback and student support during module study
Students receive rapid feedback on courseworks and class tests. Prompt marking is assisted by postgraduate support. Students are encouraged to use problem classes both to help prepare for courseworks and tests and to correct difficulties uncovered by them.
Relationship between the teaching, learning and assessment methods and the planned learning outcomes
All the examined topics will be taught in lectures. The emphasis in class is on understanding basic concepts, and on appreciating the mathematical approach to proof and to problem solving. This will be further practised in the courseworks and tests. The primary purpose of the final examination is to encourage and test the integration of learning and understanding across the whole range of topics taught.
Resources
Core Resources
- Johnsonbaugh R, Discrete Mathematics, Macmillan 19862008 edition on order - Jan 2008. [Library] [Shops]
Background Resources
- Truss J, Discrete Mathematics for Computer Scientists (2nd Edition), Addison Wesley 1999 [Library] [Shops]
- Ross K A and Wright C R B, Discrete Mathematics, Fifth Edition, Prentice-Hall 2003 [Library] [Shops]
- Biggs N L, Discrete Mathematics (2nd Edition), Clarendon Press, Oxford 2002 [Library] [Shops]
- Grossman P, Discrete Mathematics for Computing (2nd Edition), Palgrave Macmillan, 2002 [Library] [Shops]
- Rosen K H, Discrete Mathematics and Its Applications, Fourth Edition, 1999 [Library] [Shops]
Notes
Importance of this course
Generally, the Computer Science degrees at Southampton are concerned with practice as much as theory, hence the significant component of continuous assessment, or coursework. However, practice is founded on theory. The material covered in this module is fundamental to many of the core courses in the Computer Science degrees. Moreover, much of it is outside the scope of a traditional mathematics A-level, since computing is built on discrete mathematics rather than the continuous mathematics that you will have studied so far.
So the purpose of this module is to introduce you to the underlying mathematical theory of the integers, sets (arbitrary collections), graphs, trees and functions, all of which are important to further study of subjects like data structures and algorithms. We will study the principles of logic which underpin computation. We will also introduce some basic ideas about proof. This is entirely appropriate in computing. When you write a program, it is the responsibility of the computer to carry out its instructions and do the calculations. Your responsibility is to make sure that the instructions are correct. One of the important techniques we study will be proof by induction. This turns out to have a strong relation to the idea of recursion which is central to much of computer science.
Taught to
COMP1007
Pt I BSc Computer Science (Compulsory)Pt I MEng Computer Science with Artificial Intelligence (Compulsory)
Pt I MEng Computer Science (Compulsory)
Pt I MEng Computer Science with Distributed Systems & Networks (Compulsory)
Pt I MEng Computer Science with Image and Multimedia Systems (Compulsory)
Pt I MEng Computer Science with Mobile and Secure Systems (Compulsory)
ECS Socrates Students (Optional)
Pt I BEng Software Engineering (Compulsory)
Non-existing cohort: "seMEng1" (Compulsory)
Students who are not registered on an ECS approved programme may take this module subject to meeting its pre-requisites and the availability of resources. To confirm this, please can you contact the module leader (as listed above) in the first instance. They will then refer you on to the appropriate director of studies for formal approval of your selection.