This module is inactive in the selected year. The information shown below is for the academic year that the module was last running in, prior to the year selected.
2015/16 Undergraduate Module Catalogue
COMP2941 Algorithms II
20 creditsClass Size: 85
Module manager: Dr Haiko Muller
Email: H.Muller@leeds.ac.uk
Taught: Semesters 1 & 2 (Sep to Jun) View Timetable
Year running 2015/16
Pre-requisite qualifications
COMP 1740 Mathematics for Computing or equivalent MATH modulesPre-requisites
| COMP1551 | Core Programming |
| COMP1641 | Algorithms I |
| COMP1740 | Mathematics for Computing |
This module is not approved as a discovery module
Objectives
On completion of this module, students should be able to:- Understand how to compute with vectors and matrices;
- Appreciate the role of numerical computation in computer science;
- Choose a computational algorithm appropriately, accounting for issues of accuracy, reliabilty and efficiency;
- Understand how to assess/measure the error in a numerical algorithm and be familar with how such errors are controlled;
- Understand the fundamental techniques for the deisgn of efficient algorithms;
- Demonstrate how these algorithms are analysed;
- Understand several advanced data structures, their efficient implementation and applications;
- Understand how these algorithms and data structures relate to the central practical problems of modern computer science.
Skills outcomes
Python
Syllabus
Semester 1:
Vectors and matrices: vectors, vector operations (sum, scalar multiplication, difference, dot product, norm), matrices, matrix operations (sum, scalar multiplication, difference, multiplication), identity matrix; inverse of a matrix.
Approximation: converting a real-world problem, via a mathematical model, to a form which can be understood by a computer; discretising a continuous model; measuring, analysing and controlling approximation errors; balancing accuracy and efficiency. Static systems: simple iterative methods for solving nonlinear scalar equations; direct and iterative methods for solving linear systems of equations.
Evolving systems: differentiation as rate of change and as the limit of a gradient (including derivatives of simple functions); initial value ordinary differential equations, simple methods for initial value problems.
Semester 2:
Principles of algorithm design:
Representations of graphs: adjacency list, adjacency matrix. Depth- and breadth-first search traversals, topological sort, shortest-paths algorithms (Dijkstra's and Floyd's algorithm), minimum spanning tree (Prim's and Kruskal's algorithms, union-find data structure). Algorithmic strategies: greedy algorithm, divide-and-conquer, dynamic programming. Recurrence equations, Master theorem. Strassen's algorithm for matrix multiplication. Hashing, heaps, binary search trees, balanced search trees
Teaching methods
| Delivery type | Number | Length hours | Student hours |
| Example Class | 20 | 1.00 | 20.00 |
| Class tests, exams and assessment | 1 | 2.00 | 2.00 |
| Class tests, exams and assessment | 1 | 3.00 | 3.00 |
| Lecture | 44 | 1.00 | 44.00 |
| Private study hours | 131.00 | ||
| Total Contact hours | 69.00 | ||
| Total hours (100hr per 10 credits) | 200.00 | ||
Private study
- Taught session preparation: 36 hours- Taught session follow-up: 36 hours
- Self-directed study: 14 hours
- Assessment activities: 45 hours
Opportunities for Formative Feedback
Attendance and summative&formative assessment.Methods of assessment
Coursework
| Assessment type | Notes | % of formal assessment |
| Assignment | Practical Programming Task | 0.00 |
| Assignment | Practical Programming Task | 0.00 |
| Problem Sheet | Problem Sheet 1 | 5.00 |
| Problem Sheet | Problem Sheet 2 | 5.00 |
| Problem Sheet | Problem Sheet 3 | 2.50 |
| Problem Sheet | Problem Sheet 4 | 2.50 |
| Problem Sheet | Problem Sheet 5 | 2.50 |
| Problem Sheet | Problem Sheet 6 | 2.50 |
| 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) | 3 hr 00 mins | 80.00 |
| Standard exam (closed essays, MCQs etc) | 2 hr 00 mins | 0.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 websiteLast updated: 05/11/2015
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