This module is discontinued 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 exam

Methods 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 website

Last updated: 06/05/2015

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