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: Computer Algebra (INFR10009)

Course Outline
SchoolSchool of Informatics CollegeCollege of Science and Engineering
Course typeStandard AvailabilityAvailable to all 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/ca Taught in Gaelic?No
Course descriptionComputer 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 (not applicable to Visiting Students)
Pre-requisites It is RECOMMENDED that students have passed Mathematics for Informatics 3 (MATH08013) AND Mathematics for Informatics 4 (MATH08025)
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. 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.
Additional Costs None
Information for Visiting Students
Pre-requisitesNone
Displayed in Visiting Students Prospectus?Yes
Course Delivery Information
Delivery period: 2011/12 Semester 2, Available to all students (SV1) WebCT enabled:  No Quota:  None
Location Activity Description Weeks Monday Tuesday Wednesday Thursday Friday
CentralLecture1-11 12:10 - 13:00
CentralLecture1-11 12:10 - 13:00
First Class Week 1, Monday, 12:10 - 13:00, Zone: Central. AT M1
Exam Information
Exam Diet Paper Name Hours:Minutes
Main Exam Diet S2 (April/May)2:00
Summary of Intended Learning Outcomes
1 - Use the computer algebra system Maple as an aid to solving mathematical problems.
2 - Design and implement in Maple appropriate algorithms from constructive mathematical solutions to problems.
3 - Discuss the overall design of the computer algebra system Maple.
4 - Evaluate the results obtained from a computer algebra system and discuss possible problems.
5 - Explain the gap between ideal solutions and actual systems (the need to compromise for efficiency reasons).
6 - Describe and evaluate data structures used in the computer representation of mathematical objects.
7 - Discuss the mathematical techinques used in the course and relate them to computational concerns.
8 - Discuss and apply various advanced algorithms and the mathematical techniques used in their design.
9 - 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).
Assessment Information
Written Examination 80
Assessed Assignments 20
Oral Presentations 0

Assessment
Three sets of exercises involving the use of Maple as well as pencil and paper work.

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 * Maple: general design principles, user facilities, data structures, use of hashing, etc.
* Brief comparison of systems.
* Algebraic structures: overview, basic concepts and algorithms.
* Arbitrary precision operations on integers, rationals, reals, polynomials and rational expressions.
* Importance of greatest common divisors and their efficient computation for integers and univariate polynomials (using modular methods).
* Multivariate polynomial systems: solution of sets of equations over the complex numbers; construction and use of Groebner bases; relevant algebraic structures and results.
* Reliable solution of systems of polynomial equations in one variable; Sturm sequences, continued fractions method.

Relevant QAA Computing Curriculum Sections: Data Structures and Algorithms, Simulation and Modelling, Theoretical Computing
Transferable skills Not entered
Reading list * J. von zur Gathen and J. Gerhard, Modern Computer Algebra, Cambridge University Press, second edition, 2003.
* K. O. Geddes, S. R. Czapor and G. Labahn, Algorithms for Computer Algebra, Kluwer Academic Publishers (1992).
* J.H. Davenport, Y. Siret and E. Tournier, Computer Algebra; systems and algorithms for algebraic computation, Academic Press 1988.
* D.E. Knuth, Seminumerical Algorithms, second dedition, Addison-Wesley 1981.
Study Abroad Not entered
Study Pattern Lectures 20
Tutorials 0
Timetabled Laboratories 0
Non-timetabled assessed assignments 24
Private Study/Other 56
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