Algorithmic Problem Solving
News
Watch this space for announcements.
 10/12/12. Coursework 5, deadline extension. I will present solutions to coursework 5 in tomorrow's lecture. Solutions that are handed in before the lecture will be marked.
 10/12/12. Revision handout now available. See lecture schedule below for copies of revision handout (also handed out in today's lecture).
 15/11/12. Change in schedule. Because I had to miss the lectures at the beginning of this week, I have revised the schedule. In particular, the handin deadline for coursework 4 has been put back. See below for details. My apologies for any inconvenience.
 05/11/12. Tuesday lectures moved to LT3. Effective immediately. Following complaints about C33, the University's Timetabling section has agreed to move the Tuesday 9am lecture to LT3 in the Exchange Building. This change will take place immediately. The lecture on Tuesday 6th November was originally cancelled but I will now use this opportunity to repeat the Monday 5 November feedback lecture.
 22/10/12. Catchup Tutorials. There will be an extra catchup tutorial for anyone who with good cause is unable to attend a particular tutorial. The catchup tutorials will take place in alternating weeks, in the week following the regular tutorial, on Tuesday at 11am in C81a, Computer Science Building. (For example, if you are ill in the week beginning 29th October, you may book to attend the catchup tutorial on 6th November.) This is a very small room so please contact Khin in advance before attending; otherwise you may be turned away. The first catchup tutorial will take place tomorrow (23/10/12).
 22/10/12 The move of Monday tutorials to Thursday is now confirmed. NB. As last week, the Monday, 9.0010.00 tutorial will now take place on Thursdays from 09.0010.00 in C60 (CS building); the Monday 14.00:15.00 tutorial will now take place on Thursday from 15.00:16.00 in JCBSSOUTHA07 (Business School South, room A07).
 16/10/12 The tutorials WILL go ahead this week. Students allocated to the 9am, Thursday tutorial in the Dearing building should go to C60 instead. Apologies for the inconvenience.
 16/10/12 Skeletons for lecture on 16th October added.
 11/10/12 Monday tutorials to move to Thursday. Because those with tutorials scheduled for Monday will always be two lectures behind, I have arranged for them to move to Thursdays. The Monday, 9.0010.00 tutorial will move to Thursday, 09.0010.00 in C60, CS building. The Monday 14.00:15.00 tutorial will move to Thursday 15.00:16.00, C60, CS building. In case anyone does not receive this information on time, the tutorials on Monday 15th October will go ahead as scheduled but will also be repeated on Thursday 18th October. If anyone is inconvenienced by the change of time, please contact Khin Lwin to arrange a switch.
 09/10/12 Summary of yesterday's lecture added here.
 27/09/12 Website is being updated ready for the new academic year. Information may be out of date!
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 wellchosen problems. Appropriate mathematical skills are introduced in the same problemdriven way.
 Convenor: Roland Backhouse
 Module Code: G51APS
 Duration: Autumn 2012, Semester 1
 Method and frequency of class: Two lectures per week:
 Monday, 16:0017:00 in JCEXCHGEC.C33+
 Tuesday, 09:0010:00 in JCEXCHGELT3+
 Method of assessment: Unseen 2 hour examination (100%)
Forum
The CS School provides a forum where you can ask questions. If you want to access it, please follow the following link:Literature

The book Algorithmic Problem Solving is available from the publisher John Wiley and amazon. It is also available in the University bookshop. 
The following texts provide supplementary reading.
 How to Solve It, George Polya. 2nd ed., Princeton University Press, 1957, ISBN 0691080976.
 Algorithmic Puzzles, Anany Levitin, Maria Levitin, Oxford University Press, 2012.
 PuzzleBased Learning. An Introduction to Critical Thinking, Mathematics, and Problem Solving, Zbigniew Michalewicz and Matthew Michalewicz, Hybrid Publishers, 2008
 The Art and Craft of Problem Solving, Paul Zeitz, John Wiley and Sons, Inc. , 1999.
Lectures
The lecture overview below is tentative. On some topics we may progress slower or faster than scheduled. If so, any references to lecture numbers will always refer to the content listed below, regardless of the date the lecture took place. Also, some topics may change slightly, especially towards the end.
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 in the table below. Remember to bring printed copies of these to every lecture.
Lecture  Date  Content  Skeleton  
1  1st October  Administrative Details and Introduction  Introduction  
2  2nd October  Invariants  Invariants  
3  8th October  Invariants (cont.)  Boxes Problem  Summary  
4  9th October  Crossing a River.  Nervous Presidents  Problem Decomposition 
5  15th October  Brute Force Search  Bruteforce Search  3x2 Nervous Presidents, State Transition Diagram 
6  16th October  Sets, Permutations and Combinations  Sets, Permutations and Combinations  
7  22nd October  Solutions Feedback on coursework 1.  
8  23rd October  Logic Puzzles  Logic Puzzles  
9  29th October  Logic Puzzles (Cont.)  
10  30th October  Logic Puzzles (Cont.)  
11  5th November  Solutions Feedback on Coursework 2  
12  6th November  Repeat of lecture on 5th November. New location: LT3.  
13  12th November  Lecture cancelled because of illness  
14  13th November  Lecture cancelled because of illness  
15  19th November  Games  Games  
16  20th November  Games (cont.)  Game Sum  
17  26th November  Games (Cont.)  
18  27th November  Induction  Induction  Tower of Hanoi 
19  3rd December  Tower of Hanoi  
20  4th December  Solutions Feedback on coursework 3  Solutions Feedback on coursework 4.  
21  10th December  Revision  Revision  
22  11th December  Solutions Feedback on coursework 5.  Revision. StateSpace Explosion.  
Lecture Notes
The primary source of additional reading is the book Algorithmic Problem Solving. It is possible that additional material may be placed here.
Coursework
Coursework is nonassessed but will be marked for feedback purposes. Examination questions will be substantially, but not exclusively, based on the coursework. On account of the tight feedbackdeadlines, coursework handed in late will not be marked. (Non)completion of coursework will be monitored and reported.
Coursework can be downloaded by clicking on the links below. The dates shown are the deadlines for submission. Model solutions will not be made available electronically but will be distributed in hardcopy form in lectures and tutorials.
 12 October 2012 Coursework 1 (Invariants).
 26 October 2012 Coursework 2 (River Crossing).
 9 November 2012 Coursework 3 (Logic Puzzles).
 30 November 2012 Coursework 4 (Games).
 14 December 2012 Coursework 5 (Induction).
Tutorials
Tutorials for this module are being coordinated by Khin Lwin (psxktl at nottingham.ac.uk).
There are five tutorial groups, each at a different time in the week. Each student is assigned to one group. See the tutorial groups to determine which group you are in. If you have been allocated to a tutorial group that you cannot attend because of timetable clashes, you are welcome to change to another group.
Model Solutions to Past Examination Papers
Past examination papers can be found here (access restricted to Nottingham University students).
Local copies and model solutions to recent papers can be found below.
Getting Help
If you have any questions on the course, please arrange to see one of the tutorial assistants or see the module convenor immediately after the lecture or in his office (room B30).
If you do have difficulty getting hold of someone, send an email to rcb at cs.nott.ac.uk suggesting a time and day that you would like to come. Make sure your email includes your name and states that it is about G51APS and is sent from a University email account. (Emails from nonuniversity accounts may be spammed.) Please keep email traffic to a minimum.