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. Each student also has one examples class in that period. 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.

Blackboard

Course notes will be available via these pages. There is also an area on the University's Blackboard Site for the course where solutions will be released. 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 complexity, correctness and computability.

Please see the first half of the notes for a thorough introduction to the topics being covered and additional information such as recommended reading.

Course notes

These notes contain a lot of new material and it is likely that they will also contain some mistakes. 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. A list of the corrected mistakes can be found here

The notes contain the exercises for the examples classes and solutions will be posted on Blackboard.


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.

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