This module is not currently running 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.
2014/15 Undergraduate Module Catalogue
COMP1641 Algorithms I
20 creditsClass Size: 90
Module manager: Dr Natasha Shakhlevich
Email: n.shakhlevich@leeds.ac.uk
Taught: Semesters 1 & 2 (Sep to Jun) View Timetable
Year running 2014/15
This module is not approved as a discovery module
Objectives
On completion of this module, students should be able to:- understand the term 'model of computation' and be familiar with a
number of standard models
- understand the theory of automata and grammars, and its applications
- understand the basics of computability, and demonstrate the existence
of undecidable problems
- understand the operation of iterative and recursive algorithms;
- understand the importance of algorithm analysis in computing;
-analyse the time complexity of several types of algorithms;
- appreciate the importance of data structures and their implementation.
Learning outcomes
Syllabus
Formal languages and automata:
Regular languages: finite automata (DFA, NFA), regular expressions,
linear grammars, equivalence of models, minimisation of DFA, pumping lemma for regular languages.
Context-free languages: context-free grammars and normal forms, parsing and parse trees, ambiguity, push-down automata. Recursive languages: Turing machines, the Church-Turing thesis, recursive and recursively enumerable languages, the halting problem.
Algorithms and their analysis: Iterative algorithms, recursive algorithms, worst-case analysis of algorithms, big O, simple recurrence relations. Searching and sorting algorithms: sequential and binary search, selection sort, insertions sort, quicksort, mergesort, heapsort. Simple data structures: arrays, lists, stacks, queues, heaps, search trees and hash tables.
Teaching methods
Delivery type | Number | Length hours | Student hours |
Lecture | 44 | 1.00 | 44.00 |
Tutorial | 22 | 1.00 | 22.00 |
Private study hours | 134.00 | ||
Total Contact hours | 66.00 | ||
Total hours (100hr per 10 credits) | 200.00 |
Opportunities for Formative Feedback
Progress is monitored through tutorial worksheets, regular coursework and mock examMethods of assessment
Coursework
Assessment type | Notes | % of formal assessment |
Problem Sheet | PS 1 | 10.00 |
Problem Sheet | PS 2 | 2.50 |
Problem Sheet | PS 3 | 2.50 |
Problem Sheet | PS 4 | 2.50 |
Problem Sheet | PS 5 | 2.50 |
Total percentage (Assessment Coursework) | 20.00 |
August resit is 100% examination.
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 |
Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated
Reading list
The reading list is available from the Library websiteLast updated: 06/05/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