2016/17 Undergraduate Module Catalogue

COMP1511 Introduction to Discrete Mathematics

10 creditsClass Size: 165

Module manager: Kristina Vuskovic
Email: k.vuskovic@leeds.ac.uk

Taught: Semester 2 (Jan to Jun) View Timetable

Year running 2016/17

This module is not approved as a discovery module

Module summary

Discrete mathematics studies finite mathematical structures, and it provides mathematical foundations for many computer science courses, including algorithms, data structures, database theory, automata theory, formal languages, compilers, security. This module begins with the study of combinatorics. We learn how to count objects with certain properties, which is, for example, essential in determining the complexity of algorithms. We learn general techniques for solving problems such as: how many different meals one can order from a menu in a restaurant, or calculating the number of different full houses in poker, or determining how many different nonnegative integer solutions there are to a given linear equation. Counting is also central to discrete probability theory, which is the next topic we cover. Here we learn how to answer questions such as: what is the probability of getting a full house in poker, or if two dice are rolled and we are told that at least one die is 5, what is the probability that we get a sum of 10? Finally, we give an introduction to graph theory, which is then further studied and used in other modules. Graphs consist of vertices and edges that connect these vertices. They are a powerful tool that can model a wide variety of problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, linguistics, and so on. For example graphs can be used to determine whether a circuit can be implemented on a planar circuit board, to distinguish between two chemical compounds with the same molecular formula but different structures, to study the structure of the World Wide Web, or to determine a shortest path between two cities.

Objectives

On completion of this module, students should be able to: understand and be proficient in applying some of the mathematical concepts and techniques that are fundamental to computing, and in particular those that fall within the areas of combinatorics, discrete probability theory and graph theory.

Learning outcomes
On completion of the year/programme students should have provided evidence of being able to:
- demonstrate a familiarity with the basic concepts, information, practical competencies and techniques which are standard features of the discipline;
- be able to interpret and evaluate the underlying concepts and principles of the discipline;
- evaluate qualitative and/or quantitative data;
- demonstrate an ability to evaluate the appropriateness of different approaches to problem solving associated with the discipline;
- appreciate their strengths and weaknesses as learners;
- demonstrate computational thinking including its relevance to everyday life;
- operate computing equipment effectively, taking into account its logical and physical properties.

Syllabus

Combinatorics: multiplication principle, addition principle, permutations with unlimited repetition, combinations with unlimited repetition.
Discrete probability theory: experiment, sample space, event, finite probability space, probability of an event, equiprobable spaces, conditional probability, independent events, variance, binomial distribution.
Graph theory: graph models, graph isomorphism, vertex degrees, paths and cycles, Euler's theorem (Euler cycles and paths), bipartite graphs, trees.

Teaching methods

Delivery type	Number	Length hours	Student hours
Class tests, exams and assessment	1	2.00	2.00
Lecture	22	1.00	22.00
Tutorial	10	1.00	10.00
Private study hours			66.00
Total Contact hours			34.00
Total hours (100hr per 10 credits)			100.00

Private study

Taught session preparation: 18 hours
Taught session follow-up: 18 hours
Self-directed study: 7 hours
Assessment activities: 23 hours

Opportunities for Formative Feedback

Attendance and formative assessment

Methods of assessment

Coursework

Assessment type	Notes	% of formal assessment
Problem Sheet	Problem Sheet	5.00
Problem Sheet	Problem Sheet	5.00
Problem Sheet	Problem Sheet	5.00
Problem Sheet	Problem Sheet	5.00
Total percentage (Assessment Coursework)		20.00

This module is re-assessed by exam only.

Exams

Exam type	Exam duration	% of formal assessment
Standard exam (closed essays, MCQs etc)	2 hr 00 mins	80.00
Total percentage (Assessment Exams)		80.00

This module is re-assessed by exam only.

Reading list

The reading list is available from the Library website

Last updated: 07/03/2017

Disclaimer

Browse Other Catalogues

• Undergraduate module catalogue
• Taught Postgraduate module catalogue
• Undergraduate programme catalogue
• Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD