СÀ¶ÊÓƵ

School of Engineering and Informatics (for staff and students)

Program Analysis (G6017)

Program Analysis

Module G6017

Module details for 2021/22.

15 credits

FHEQ Level 5

Module Outline

Part 1: Foundations
The first part of the module introduces the idea of the asymptotic analysis of algorithms, and in particular we will consider the following: specifying a problem; the notion of an algorithm and what it means for an algorithm to solve a problem; the upper, lower and tight asymptotic bounds associated with an algorithm; the best-, worst- and expected-case analysis of an algorithm; the lower bound for a problem.

In the remainder of Part 1 we consider a number of important data structures, with particular emphasis on priority queues and the generic graph data structure. Several basic graph algorithms will be considered, in particular: depth-first search of graphs; breadth-first search of graphs; and topological sorting of directed acyclic graphs.
Part 2: Generic Design Paradigms
In part 2 we will consider four of the most important methods used as the basis for algorithm design: greedy methods; divide and conquer approaches; dynamic programming; and network flow.

In considering these generic design paradigms we will look at a number of well-known problems, including: interval scheduling; single source shortest path; minimum spanning tree; Huffman codes construction; weighted interval scheduling; subset sum; sequence alignment; network flow; and bipartite matching.

Library

J. Kleinberg and E. Tardos: Algorithm Design, Addison Wesley, 2005. International Student Edition.
This text is recommended because: (a) it is the one that the course will most closely follow (we will be covering parts of the material that is presented in the first seven chapters); and (b) the concepts are presented using a wide range of reasonably realistic problems.
Alternative text
Michael T. Goodrich and Roberto Tamassia, Data Structures and Algorithms in Java, John Wiley & Sons, Inc.
This is a more traditional algorithms textbook might be more to your taste.
Reference text
Thomas H Cormen, Charles E Leiserson, Ronald L Rivest and Clifford Stein, Introduction to Algorithms, Second Edition, MIT Press, 2001.
This is a good reference book on algorithms.

Module learning outcomes

Given a novel problem specification, determine an appropriate style of algorithm to deploy for that problem.

Analyse the asymptotic efficiency of an algorithm, distinguishing best-, worst- and expected-cases.

Design and implement algorithmic solutions to problems based on greedy, dynamic programming and network flow approaches.

Express an algorithm using abstract pseudo-code rather than using a particular programming language.

TypeTimingWeighting
Computer Based ExamSemester 1 Assessment75.00%
Coursework25.00%
Coursework components. Weighted as shown below.
Problem SetT1 Week 6 50.00%
Problem SetT1 Week 11 50.00%
Timing

Submission deadlines may vary for different types of assignment/groups of students.

Weighting

Coursework components (if listed) total 100% of the overall coursework weighting value.

TermMethodDurationWeek pattern
Autumn SemesterLecture2 hours22222222222
Autumn SemesterWorkshop1 hour01111111111

How to read the week pattern

The numbers indicate the weeks of the term and how many events take place each week.

Dr Kingsley Sage

Assess convenor
/profiles/129351

Please note that the University will use all reasonable endeavours to deliver courses and modules in accordance with the descriptions set out here. However, the University keeps its courses and modules under review with the aim of enhancing quality. Some changes may therefore be made to the form or content of courses or modules shown as part of the normal process of curriculum management.

The University reserves the right to make changes to the contents or methods of delivery of, or to discontinue, merge or combine modules, if such action is reasonably considered necessary by the University. If there are not sufficient student numbers to make a module viable, the University reserves the right to cancel such a module. If the University withdraws or discontinues a module, it will use its reasonable endeavours to provide a suitable alternative module.

School of Engineering and Informatics (for staff and students)

School Office:
School of Engineering and Informatics, СÀ¶ÊÓƵ, Chichester 1 Room 002, Falmer, Brighton, BN1 9QJ
ei@sussex.ac.uk
T 01273 (67) 8195

School Office opening hours: School Office open Monday – Friday 09:00-15:00, phone lines open Monday-Friday 09:00-17:00
School Office location [PDF 1.74MB]