Computer Algebra (U01955)

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

Computer graphics uses various shapes such as ellipsoids for modelling. Consider the following problem: we are given an ellipsoid, a point from which to view it, and a plane on which the viewed image is to appear. The problem is to find the contour of the image as an equation (a numerical solution is not good enough for many applications). The problem does not involve particularly difficult mathematics, but a solution by hand is very difficult in general. This is an example of a problem which can be solved fairly easily with a computer algebra system. These systems have a very wide range of applications and are useful both for routine work and research. From a computer science point of view they also give rise to interesting problems in implementation and the design of algorithms. The considerations here are not only theoretical but also pragmatic: for example there is an algorithm for polynomial factorization which runs in polynomial time; however systems do not use this since other (potentially exponential time) methods work faster in practice. The design of efficient algorithms in this area involves various novel techniques. The material of the course will be related whenever possible to the computer algebra system Maple, leading to a working knowledge of the system.

Entry Requirements

? Pre-requisites : Mathematics for Informatics 3 Mathematics for Informatics 4 Successful completion of Year 3 of an Informatics Single or Combined Honours Degree, or equivalent by permission of the School. Familiarity with computer programming and data structures will be assumed. The course will contain an overview of less familiar algebra, as well as some new concepts.

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:
-Use the computer algebra system Maple as an aid to solving mathematical problems.
-Design and implement in Maple appropriate algorithms from constructive mathematical solutions to problems.
-Discuss the overall design of the computer algebra system Maple.
-Evaluate the results obtained from a computer algebra system and discuss possible problems.
-Explain the gap between ideal solutions and actual systems (the need to compromise for efficiency reasons).
-Describe and evaluate data structures used in the computer representation of mathematical objects.
-Discuss the mathematical techinques used in the course and relate them to computational concerns.
-Discuss and apply various advanced algorithms and the mathematical techniques used in their design.
-Use the techniques of the course to design an efficient algorithm for a given mathematical problem (of a fairly similar nature to those discussed in the course).