Algorithms in Practice (U03217)

? Credit Points : 10 ? SCQF Level : 10 ? Acronym : INF-4-AP

Algorithms (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

? This course is not available to visting students.

? Pre-requisites : Algorithms and Data Structures Successful completion of Year 3 of an Informatics Single or Combined Honours Degree, or equivalent by permission of the School.

Subject Areas

Home subject area

Theoretical Computer Science, (School of Informatics, Schedule O)

Delivery Information

? Normal year taken : 4th year

? Delivery Period : Not being delivered

? Contact Teaching Time : 2 hour(s) per week for 10 weeks

Summary of Intended Learning Outcomes

It is anticipated that students who successfully complete the course will be able to:
- Discuss the obstacles to efficient exact solutions to certain problems.
- Given a problem related to those covered in the course assess its likely algorithmic difficulty.
- Given a proposed algorithm for a problem assess its suitability in terms of correctness and efficiency.
- Discuss notions of approximation for optimisation problems.
- Develop and justify appropriate algorithms for problems related to ones discussed in the course.