MAS336 Computational Problem Solving

Course Organiser Dr Francis J. Wright; click to contact me or report problems with this web site.

This page was last updated on 23 February 2007.

Synopsis

Lectures

This course is somewhere between conventional lecture, reading and project courses.  There will be some informal lectures, although probably not all scheduled lectures will be used once the course is under way.  Lectures start on Tuesday 9^th January 2007 and the timetable is as follows:

But note that I do not plan to use the Wednesday lecture after the first week.  Full project descriptions are available on the web; see below.

Recommended text book

Computing with Maple by Francis Wright [Chapman & Hall / CRC Press, September 2001], price £25.

This should be available from the College bookshop, Amazon, etc. and the College Library should have two copies in the Short Loan Collection and two copies on One Week Loan.

Syllabus

The problems currently available are as follows.  After each problem title are links giving details of the problem as Maple worksheet (mws) and Adobe Portable Document Format (pdf) files, or a brief outline problem description as an html file.  The marks for the best five solutions will contribute 20% each to the final mark for the course, and there will be a penalty for late submission.

Main problems discussed in lectures:

1. Pythagoras & Fermat (mws, pdf)
   Compute and display Pythagorean triples and numerically investigate Fermat's Last Theorem.
   Submission deadline Friday 2nd February 2007.
2. Word Search (mws, pdf)
   Generate and solve random rectangular word-search puzzles.
   Submission deadline Friday 16th February 2007.
   (Try this online word search.)
3. Eight Queens (mws, pdf)
   Compute and display all possible distinct ways to place eight queens on a chess board so that none threatens any other, taking account of symmetry.
   Submission deadline Friday 2nd March 2007.
4. Magic Squares (mws, pdf)
   Compute and display all possible distinct 3´3 magic squares, taking account of symmetry.
   Submission deadline Friday 16th March 2007.
5. Game of Life (mws, pdf)
   Animate Conway's "Game of Life" cellular automaton.
   Submission deadline Friday 30th March 2007 (end of semester).
   (For additional background, see Edwin Martin's web site.  Local copies of Edwin Martin's Windows executable and Martin Gardner's original Scientific American article are also available.)

Alternative problems not discussed in lectures:

These problems are optional alternatives to the main problems above, but very little guidance will be provided.  The submission deadline for all alternative problems is Friday 30th March 2007 (end of semester).

6. Number Spirals (html)
   Compute and display "number spirals" at different scales and then superimpose some "product curves".
7. Linear Clock (html)
   Display a static "linear clock" that shows the current (or a specified) time and date.

Submission requirements

The final deadlines above are as late as possible to allow some flexibility, but I recommend that you aim to complete each project about a week before the deadline.  There will be a penalty of 1 mark (out of the maximum of 20) for each weekday by which a project report is submitted late.  I will mark each project and provide you with some feedback in the lectures as quickly as possible.

Your submission for each project should consist of one or more programs that solve the problem together with a discussion of your approach.  Both components are important.  It is best if your submission for each project consists of a single Maple worksheet.  Please submit each project report printed on paper and by email as an attached file; I must receive both versions by the final deadline.  Paper submissions can be given to me either in lectures or in my office, Maths B54, during my office hours, which are 10:00 am – 12:00 noon and 2:00 pm – 5:00 pm most days unless I have another commitment; see my contact details.  Email submissions should include the course title, Computational Problem Solving, and your name in your email and use the filename convention "Surname - Problem Title", e.g. "Wright - Pythagoras & Fermat" (or something very similar), so that I can save all submissions in a logical and unambiguous way.

All of your submissions must be neatly presented and 40% of the marks will be allocated for presentation.  Do not repeat information that I have given you in the problem descriptions, but do include your own ideas, such as any theoretical investigations you made, your choice of data structures, interesting details of your algorithms and implementations, any testing that you did, any considerations of efficiency.  Some marks will be awarded for the general clarity of your submissions and for reasonable efficiency and elegance of your programs.  Take care over your spelling and grammar; Maple 9 and later versions include a spelling checker, although beware that the default dictionary is for Canadian rather than British English!

Mark scheme

This general mark scheme applies to all the problems:

• 60% (12 marks) overall for a correct solution – see the problem description for further details;
• 40% (8 marks) for presentation and discussion:
  • 10% (2 marks) for efficiency;
  • 10% (2 marks) for elegance, clarity and # comments within the Maple code;
  • 20% (4 marks) for general discussion, e.g. of design choices, explanation of algorithms and implementation, investigation of alternative approaches, mathematical analysis where appropriate, informal complexity considerations.

Further Guidance

Which version of Maple should I use?