THE UNIVERSITY of EDINBURGH

DEGREE REGULATIONS & PROGRAMMES OF STUDY 2011/2012
- ARCHIVE for reference only
THIS PAGE IS OUT OF DATE

University Homepage
DRPS Homepage
DRPS Search
DRPS Contact
DRPS : Course Catalogue : School of Informatics : Informatics

Undergraduate Course: Algorithms in Practice (INFR10028)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Course typeStandard AvailabilityNot available to visiting students
Credit level (Normal year taken)SCQF Level 10 (Year 4 Undergraduate) Credits10
Home subject areaInformatics Other subject areaNone
Course website http://www.inf.ed.ac.uk/teaching/courses/ap Taught in Gaelic?No
Course descriptionAlgorithms (and data structures) are fundamental to all computing. Any given problem will have many possible algorithms unless it is computationally unsolvable. It is therefore important to have criteria for choosing between competing algorithms. Various technical tools (e.g., runtime analysis) are covered in the third year pre-requisite course. However there remains the difficulty of what can be done with problems that do not seem to have algorithms that can be guaranteed to be efficient for all inputs. This course will focus on a few areas and discuss techniques for addressing such problems as well as pragmatic considerations in choosing algorithms. In addition students will have the opportunity to extend their knowledge of algorithms in the area of Computational Geometry. The course overall is practically based but theory informed.
Entry Requirements (not applicable to Visiting Students)
Pre-requisites Students MUST have passed: Algorithms and Data Structures (INFR09006)
Co-requisites
Prohibited Combinations Other requirements Successful completion of Year 3 of an Informatics Single or Combined Honours Degree, or equivalent by permission of the School.
Additional Costs None
Course Delivery Information
Not being delivered
Summary of Intended Learning Outcomes
1 - Discuss the obstacles to efficient exact solutions to certain problems.
2 - Given a problem related to those covered in the course assess its likely algorithmic difficulty.
3 - Given a proposed algorithm for a problem assess its suitability in terms of correctness and efficiency.
4 - Discuss notions of approximation for optimisation problems.
5 - Develop and justify appropriate algorithms for problems related to ones discussed in the course..
Assessment Information
Written Examination 70
Assessed Assignments 30
Oral Presentations 0

Assessment
Three sets of exercises involving the use of appropriate software. The main emphasis will be on the interpretation and appropriateness of approaches rather than writing large amounts of software. There will also be some pencil and paper elements to accompany the justification of claims.

If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year.
Special Arrangements
None
Additional Information
Academic description Not entered
Syllabus * Informal introduction to efficiency concerns, optimisation problems and related decision problems, intractability, NP-completeness.
* Theoretical and practical concerns: Linear Programming as a case study, comparison with Integer Programming techniques. Rephrasing practical problems as instances of Linear Programming and Iinteger Programming.
* Computational Geometry. Topics such as:
o Half plane intersection, relation to linear programming.
o Smallest enclosing disc of points in the plane.
o Voronoi diagrams and brief discusion of applications (e.g., in physics, astronomy, robotics); appropriate data structures (e.g., doubly connected edge lists).
o Delaunay triangulations, study of what constitutes a "good" triangulation.
* Approximation algorithms for "hard" problems covering heuristics and performance guarantees. Topics such as:
o Notions of approximation: relative error, approximation schemes.
o The vertex cover problem.
o The travelling salesman problem: with and without the triangle inequality.
o The set covering problem.
o The subset sum problem.
* Survey of various techniques, e.g., Markov chains.

Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms.
Transferable skills Not entered
Reading list * T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms (2nd Edition). MIT Press, 2002
* H. Edelsbrunner, Algorithms in Combinatorial Geometry, EATCS Monographs in Computer Science, Springer, 1987.
* F.P. Preparata and M.I. Shamos, Computational Geometry-an introduction, Springer, 1985.
* Vijay Vazirani, Approximation Algorithms, Springer 2001.
Study Abroad Not entered
Study Pattern Lectures 20
Tutorials 0
Timetabled Laboratories 0
Non-timetabled assessed assignments 30
Private Study/Other 50
Total 100
KeywordsNot entered
Contacts
Course organiserDr Amos Storkey
Tel: (0131 6)51 1208
Email: A.Storkey@ed.ac.uk
Course secretaryMiss Kate Weston
Tel: (0131 6)50 2701
Email: Kate.Weston@ed.ac.uk
Navigation
Help & Information
Home
Introduction
Glossary
Search DPTs and Courses
Regulations
Regulations
Degree Programmes
Introduction
Browse DPTs
Courses
Introduction
Humanities and Social Science
Science and Engineering
Medicine and Veterinary Medicine
Other Information
Timetab
Prospectuses
Important Information
 
© Copyright 2011 The University of Edinburgh - 16 January 2012 6:16 am