Algorithmic Problem Solving

Course Information

This module is about how to solve problems that involve the construction of an algorithm. Many problems are of this nature, so the scope is very broad. The module is structured around the basic principles of algorithm design (invariants, problem decomposition, etc.) with each principle being introduced via well-chosen problems. Appropriate mathematical skills are introduced in the same problem-driven way.

• Convenor: Roland Backhouse
• Tutors:
  • Alexandra Mendes
  • Joao Ferreira
  • Wei Chen
• Module Code: G51APS
• Duration: Autumn 2008, Semester 1
• Method and frequency of class: Two lectures per week:
  • Wednesday, 10:00-11:00 in JC-BSSOUTH-B52+
  • Friday 15:00-16:00 in JC-EXCHGE-C.LT2+
• Method of assessment: Coursework (25%) and an unseen 90-minute examination (75%)

Literature

• The Art and Craft of Problem Solving, Paul Zeitz, John Wiley and Sons, Inc. , 1999.
• Program Construction. Calculating Implementations from Specifications, Roland Backhouse, John Wiley and Sons, Inc., 2003.
• How to Solve It George Polya. 2nd ed., Princeton University Press, 1957, ISBN 0-691-08097-6.

Exercises

The problems we will be discussing are divided into groups. You will be asked to first tackle the problems on your own. Later the solution technique will be discussed in the lectures. In this way, you will have some familiarity with the problems before they are discussed in lectures, and will be in a better position to understand their solutions.

• Invariants (pdf), (ps)
• River Crossing Problems (pdf), (ps)
• Matchstick Games (pdf), (ps)
• Logic Puzzles (pdf), (ps)
• Induction (pdf), (ps)

Tutorials

Tutorials for this module will take place in the week preceding each coursework deadline. At other times, you can get help from the class tutors (Joao Ferreira,Alexandra Mendes and Wei Chen) during G51MCS classes. Please do not approach them at other times.

Each Student is assigned to a tutorial group. If you are enrolled on G51MCS your tutorial group for the two modules will be the same. If not, see the tutorials page.

Lecture Notes

2007/2008: (ps). A printed copy can be purchased from the School Office.

The dynamic nature of problem solving cannot be properly conveyed in a static text. The lectures are an important, integral part of this module. Come to them prepared to take notes and to participate actively.

Skeletons of the lectures are available below.

• Brute-force Search
• Bridge Problem
• Counting Minimal-length Paths
• Counting Edit Sequences
• Detecting a Fake Coin
• Empty Boxes
• Games
• Game Sum
• Induction
• Jealous Couples
• Logic Puzzles
• Mex Numbers - Summary
• Principle of Mathematical Induction
• Problem Decomposition
• State-space Explosion
• Tetrominoes
• Towers of Hanoi
• Triomino Summary

Remember to bring printed copies of these to every lecture.

Acknowledgement: The 1999 and 2000 calendars of the Dutch Vierkant Voor Wiskunde foundation were used for several of the examples and exercises.

Coursework

Deadlines: Friday, 31st October and Friday, 5th December.

• Coursework 1 (10%)

  The state-transition diagram for the problem of 3 couples and a boat of capacity 2 will be discussed in lectures.

• Coursework 2 (15%)

Model Solutions to Past Examination Papers

Past examination papers can be found here (access restricted to Nottingham University students).

Model solutions to these papers can be found below.

• 2005--2006
• 2006--2007
• 2007--2008

Getting Help

If you have any questions on the course that can't be handled by the class tutors (see above), please come to see me immediately after the lecture or in my office (room B30).

If you do have difficulty getting hold of me, send an email suggesting a time and day that you would like to come and see me. (But please keep email traffic to a minimum.)