COMP11212: Fundamentals of Computation

Semester 2, 2017/2018

Sean Bechhofer (Part 1) & Giles Reger (Part 2)

Schedule

There are two lectures per week, Monday at 11:00 and Tuesday at 11:00. In 2017-18 these will be held in the Roscoe Building, Theatre B. Each student also has one examples class in that period. In 2017-18 the examples classes will be in G41 in the Kilburn Building. See the organizational part of the notes and the timetable for more detail.

Reading List

Detailed notes will be distributed, but the following texts may also be useful. All can be found in the University library.

  • Introduction to the Theory of Computation (3rd Edition), Michael Sipser. CENGAGE Learning. ISBN 1-13318781-1
  • Introduction to Automata Theory, Languages, and Computation. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman
  • Logic in Computer Science: modelling and reasoning about systems. Michael Huth and Mark Ryan.

Notes

Blackboard

There is an area on the University's Blackboard Site for the course with online exercises. This has a discussion list that can be used to raise any questions you might have about the material. Please avoid discussing the specifics of assessed work (at least not until after solutions are published)

Please do not redistribute the notes. More importantly, please do not redistribute the solutions published on Blackboard.

Podcasts

Lectures are recorded using the University's Lecture Capture Podcast system. Please do not use the podcasts as a substitute for lecture attendance.


Part 1

Part 1 covers Weeks 1—5 and is taught by Sean Bechhofer.


Overview

Almost every time we use a computer the computer must make sense of what we type into it. How does it do that? How does a computer take a computer program and break it down so that it can be turned into instructions the computer can actually carry out? How can we search documents or webpages for fairly complicated pieces of text, such as all occurrences of a double typed word ("the the", for example), even across line breaks, arbitrary amounts of space, and with the first letter possibly capitalized? How can we make use of tools such as grep?

In this part of the course we study techniques that help us deal with such issues. We look at different ways of describing collections of strings, and how to transform one description into another. We also look at what these descriptions can and can't do.

Course notes

The notes, including the exercises, cover all the examinable material for this part of the course. I appreciate any feedback on the course in general as well as on the material handed out. For this purpose please email me at sean.bechhofer at manchester.ac.uk.

The notes are written in a fair amount of detail because you are expected to spend some time each week in self-study. I will not explain every detail that appears in the notes in the lectures. The lectures are there for me to introduce the big ideas, and to go through examples with you.

The notes also contain organizational information at the beginning, including a description of the format of the exam.

Copies of the notes are handed out in the first week of term. Left-over copies are deposited near the Student Support Centre as usual. If you lose your notes and no copies are left you can print them again from here.

Solutions to marked examples will be published on Blackboard.

The material for this part of the course is mathematical in nature. There is an Appendix in the notes that with a more rigorous treatment of the material. This material is examinable, but at most 10% of the final mark depends on it. Most students choose not spend time on this part, and that is fine, but if you are interested in theoretical computer science then you should work through it.

Corrections and Clarifications

We are all fallible. A list of any errors and corrections to the distributed notes will be available here.


Part 2

Part 2 of the unit runs from weeks 6—10 and is taught by Giles Reger.


Overview

The second half of the course (10 lectures) provides an introduction to the topics of computability, complexity, and correctness.

The notes provide a detailed introduction to the topics being covered and recommended reading.

Course note

The notes for this part contain all the examinable material for this part of the course. If you spot a mistake please email me at giles.reger@manchester.ac.uk. I will update the notes with corrections as they are found. See here for a list of corrections.

The style of this part is the same as Part I i.e. you are expected to spend time reading the notes and I will not cover every detail that apperas in the notes in the lectures.

Exercises for the examples classes will be posted here (they are not in the notes) and solutions will be posted on Blackboard:

Slides from the lectures will appear here after the lecture:

External resources. In the past some students have shared some websites that they have found useful/interesting. Please send anything you find useful to me to put here:

Tools

Some previous students have built some tools to help understand the material:

  • This tool is a Java tool for exploring operational semantics, correctness proofs, and Godel encodings of while programs. If you want to help improve the tool then let me know. It's quite big as it contains a theorem prover for checking constraints in correctness proofs. (Requires Java 8)
  • This tool is an interpreter for the while langauge written in C.
You are not required to use any of these tools but they may help. If you develop anything you want to share then please let me know and I'll add it here.

General Organisation

Coursework

The coursework for this unit contributes 25% of the overall mark. Each week there will be a number of exercises to be completed online via Blackboard. These must be completed by 17:00 on Friday afternoon.

In addition to the online exercises, there will be two or three exercises to be completed on paper and marked during the examples classes.

The notes also contain a number of exercises that serve as preparation for the marked work. You could also choose to leave some of these exercises for revision.

The point of the examples classes is to

  • mark your work for the week;
  • provide you with feedback for the work that you have done;
  • help you with the exercises you couldn't do.

Solutions to the exercises in the notes will be made available via Blackboard when the last examples class for a sheet has occurred.

Attendance at Examples Classes

Past experience proves the case for attendance at examples classes convincingly: Students who do the set work in each week will pass the exam. On the other hand 90% of students who failed the exam in previous years either failed the coursework or failed to even attend more than 50% of examples classes.

Examples Classes

You are expected to complete this work individually. The online exercises are marked automatically. For the examples classes, you will get a mark for the relevant exercises during the examples class. The TA may ask you to show all your work and to explain how you solved the exercise. If you cannot do this you will be considered to have plagiarized the piece of work in question and be given a mark of 0. A note will be made on your file, and for additional, or more serious, offences you will have to answer to higher authorities. Ultimately you may be expelled from the university for such offences.

Best Eight

Coursework solutions are released shortly after the examples classes. This means that there is no opportunity for extensions to the deadline.

Your final coursework mark will be calculated by taking the best eight marks from the ten weeks. This means that you can do badly in one or two sessions without impacting your final mark. If you miss more than two sessions due to ill-health or circumstances outside your control, you must submit mitigating circumstances

The examples classes are for you to get feedback on your work. They are not for you to do the work. If you attend an examples class and tell a marker that you're "not ready to be marked yet", you will get a mark of 0 for that exercise.


Exams

Exam Format

Note that the exam format has changed for academic year 17-18, with the introduction of an online component.

  • The exam will be a "hybrid" exam with a mixture of online and paper questions. It will cover both parts of the course, with online and paper questions for both Part I and Part II .
  • You must answer all parts of all questions.
  • The exam makes up 75% of the final mark, the coursework 25% (15% from online exercises, 10% from examples classes).

The department keeps a wealth of information on exams, when they are, how to prepare for them, where to find old exam papers (where they exist), etc, here.

Past Papers

The department keeps an online repository of exam papers. You can also read comments on how students performed on part 1 of each paper and where they lost marks. You can find feedback from other members of staff teaching on the unit by looking at the general feedback page.

Past Papers and Exam Feedback

Previous exam papers.

As discussed above, the exam format has changed. Past papers will still provide an indication of the kinds of question you will be asked in the exam. The weekly online questions will also prepare you for the online portion of the exam.

Note also that up until 2011/12 the course unit consisted of three Parts. Part B is no longer taught, and not relevant for your exam preparation. Part C developed into the current second part, but the past exam questions are probably not relevant any longer. Also note that the questions were shorter then. However, certainly for Part 1 the type of task that appears in the paper is still typical of what you might be asked to do.

The contents of Part II has shifted slightly over the last few years. The following questions are still relevant to the current content:

  • Questions 7 in 2009-2011 apart from the parts asking you to sketch graphs
  • Question 8 in 2009
  • Question 8b in 2010
  • Questions 7 and 8 in 2012
  • Questions 3d,3e,3f and 4 excluding 4e in 2013
  • Questions 3d, 3e and 4 in 2014
  • Questions 3 and 4 in 2015

Acknowledgements

This course unit was previously taught by Andrea Schalk and relies heavily on materials produced by Andrea.


Built with Bootstrap and Font-awesome