Run by School of Computer Science and Electronic Engineering
10 Credits or 5 ECTS Credits
Organiser: Dr David Evans
Overall aims and purpose
To introduce some of the basic ideas of discrete mathematics and algorithms: the language of sets, relations and functions; and algorithms for graphs and digraphs. Revision of elementary algebra. To introduce some of the basic ideas of calculus: continuity; differentiability; tangent lines; maxima. minima and inflections for polynomial functions.
Data structures for graphs and digraphs: adjacency lists and tables. Connectivity and isomorphism. Spanning trees in weighted graphs. Greedy algorithms: Prim and Kruskal methods for weighted spanning trees. Alphabets and strings; binary trees. Euler tours and Hamiltonian cycles.
Sets, functions, and relations: injective, surjective, bijective, inverse functions. Venn diagrams and Karnaugh maps. If time: graph morphisms; equivalence relations; partial orders. Fractions; powers; solving linear and quadratic equations in one variable.
Functions of real variables, in particular polynomial functions. Continuity. Notions of derivative and tangent line. Maxima and minima; second derivative: curvature, points of inflection. The sqrt, exp and log functions.
Inductive definitions: lists, binary trees. Simple linear difference equations.
Learning outcomes mapped to assessment criteria
Understand the formulation and solution of problems by graphs and digraphs. Understand special types of algorithm related to graph theory.
|Understand basic definitions for graphs and digraphs. Apply the specific algorithms to small weighted graphs.||Can also justify the algorithms covered.||Understands most of the definitions for graphs and digraphs. Can apply most of the algorithms for graphs, digraphs and weighted graphs listed in the course content.|
Understand, perform and develop simple algorithms.
|Perform a dry run on simple algorithm.||Develop more sophisticated algorithms and simple computational logic.||Develop simple algorithms and dry runs on more complicated algorithms.|
Use the language of set theory, relations and functions.
|Understand the meaning of set theoretic definitions using Venn diagrams and arrow diagrams.||Use set theory to solve logic problems||Can use the abstract definitions of set theory with understanding.|
Use elementary algebra.
|Can make a selected variable the subject of an equation.||Can manipulate more complicated equations and solve||Can manipulate equations and solve.|
Understand the general behavior of polynomial functions and their derivatives. Have an intuitive idea of continuity and curvature
|Find the derivative of a polynomial||Sketch, compose and differentiate more complicated functions, involving sqrt, exp and log.||Find the equation of the tangent at a point on a polynomial curve. Find maxima, minima and inflections on quadratic and cubic curves.|
Teaching and Learning Strategy
24 hours over 12 weeks
12 hours over 12 weeks
- Critical analysis & Problem Solving - Able to deconstruct and analyse problems or complex situations. To find solutions to problems through analyses and exploration of all possibilities using appropriate methods, rescources and creativity.
- Presentation - Able to clearly present information and explanations to an audience. Through the written or oral mode of communication accurately and concisely.
- Argument - Able to put forward, debate and justify an opinion or a course of action, with an individual or in a wider group setting
Subject specific skills
- Knowledge and understanding of facts, concepts, principles & theories
- Problem solving strategies
- Deploy theory in design, implementation and evaluation of systems
- Development of general transferable skills
- Defining problems, managing design process and evaluating outcomes
- Knowledge and understanding of mathematical principles
- Principles of appropriate supporting engineering and scientific disciplines
Pre- and Co-requisite Modules
- ICP-1016: Mathematics for Computing
- ICP-2033: Intro to Operating Systems
- ICP-3038: Computer Vision (20cr)
Courses including this module
Compulsory in courses:
- G400: BSC Computer Science year 1 (BSC/CS)
- G40B: BSc Computer Science (4 year with Incorporated Foundation) year 1 (BSC/CS1)
- GN41: BSC Computer Science for Business year 1 (BSC/CSFB)
- GN4B: BSc Computer Science for Business (4 year with Incorp Found) year 1 (BSC/CSFB1)
- I102: BSc Computer Science (with International Experience) year 1 (BSC/CSIE)
- GW49: BSC Creative Technologies year 1 (BSC/CT)