Steve Vickers: Introduction to Computer Science

NEWS!
Solutions and feedback on this year's exam now available.

Fundamentals of Computing: Introduction to Computer Science

Lecturer: Steve Vickers

This module is

Contents

Here is a table of the course contents, week by week.

For weeks still to come, they describe last year's syllabus and will change this year.

  1. Numbers: Number bases, binary, octal, hex; also floating point. Slides.
  2. Memory and CPUs: The two most important components of a computer, and their basic operations. Slides.
  3. Stored programs: How memory and CPU interact to execute programs stored in memory. The fetch-execute cycle, algorithmic structure using jumps, stacks and the difference between high and low level programming. Slides.
  4. Java bytecode: The Java virtual machine (JVM) and its bytecode. Slides. You can also refer to the Java Virtual Machine Specification.
  5. Objects: Objects and the heap; non-static methods and constructors. Slides.
  6. Operating systems: What they do, including memory management and multiprocessing. Slides. See Reynolds and Tymann chapter 6.
  7. Networks: Basic principles. Slides. See Reynolds and Tymann chapter 7.
  8. Invariants: Logical conditions that are kept true - instance invariants, loop invariants. The ability to maintain instance invariants, so that objects are kept in good working order, is an important security issue, and explains many of the features of both the Java language and the virtual machine. Loop invariants are a central tool in planning and debugging iterative algorithms.
    Slides; also some sample source code files: Date, Customer and BankAccount (illustrating instance invariants) and Sum (simple example of loop invariant).
    Loop invariants and binary search are covered in chapters 10 and 11 of Reasoned Programming.
  9. Loop invariants continued (last week's slides), and then Binary Search: a very good illustration of the effectiveness of loop invariants. Slides; source code file for binary search.
  10. Recursion: Methods that call themselves, either directly or indirectly. An important part of reasoning about recursion is programming by contract (week 8) and stepwise refinement.
    A substantial example is quick sort. This includes an "in-place partition" algorithm, which is a good example of the use of loop invariants, and is the subject of the second assessed coursework.
    Slides; also some sample source code files: Fib (Fibonacci numbers by recursion and repetition), Towers, TowersSolve and TowersSOUT (Towers of Hanoi, classic example of recursion) and QuickSort (recursion, and also a good example of a loop invariant).
    Recursion and Quick Sort are covered in chapters 5 and 12 of Reasoned Programming.
  11. Computability and complexity: What can be computed? (There are limits: undecidability of the Halting Problem.) How efficiently can it be done? (Does P = NP? Nobody knows.)
    Slides - note: I do not expect you to learn the undecidability proof for the halting problem. See also chapter 3 of Goldschlager and Lister.
    Here are some related links you might enjoy:

Timetable

The teaching consists of two lectures each week, both on Tuesdays:
9:00-9:50am, Room LT1 Sports and Exercise Science (Building Y14)
3:00-3:50pm, Small Lecture Theatre, Poynting (Building R13)

Continuous assessment

For the intercalated year there is no coursework -- the assessment is 100% by examination. However, you are recommended to do the MSc coursework because it will help prepare you for the exams.

For the MSc there are two pieces of continuous assessment and each contributes 5% to the module mark.

Marks, individual feedback and general feedback will be available on the School's coursework submission pages. However, you will not submit your work electronically, but in the designated box outside reception.

The first piece of continuous assessment is due for submission by 12.00, Monday 5th November. Solutions, with feedback.

The second piece of continuous assessment is due for submission by 12.00, Monday 3rd December. A second attampt is allowed, for submission by 12.00, Wednesday 9th January, and with marks capped at 17 out of 24. It is really important that you should do this if your first mark was less than 12. Here is feedback on the first answers.

Here are coursework and solutions from last year, for revision.

If you have a serious reason for not being able to complete it, then see someone from the Welfare Team. (The precise procedure is explained in the Student Handbook.) If your explanation for absence is accepted then we will ignore the exercise in the calculation of your mark.

Policy on plagiarism

You are encouraged to work in small teams during the exercise classes and to ask for help from the tutor. You will, however, have to submit your work individually. Homework exercises are of a style similar to those appearing in the May examination, and we recommend that you attempt them individually, but you may still find it helpful to discuss the assignments with others. In any case, work submitted must be formulated by yourself. If we find evidence of plagiarism then we will award zero marks, irrespective of whether you copied from others or whether your work was copied by others. More serious cases will be dealt with according to the School's policy on plagiarism.

Anonymous marking

We are required to mark anonymously wherever possible. There is no reason why we should not follow this rule for the exercises in this course. Please note, however, that this means that you always have to write your registration number on your submitted work. Scripts which do not contain the registration number will have to be ignored by us.

Final exam

The exam takes place in May and lasts 1.5-hour. It is marked on a scale from 0 to 100 but for MSc students it contributes only 90% to the module mark.

Its format is as follows.

  • One compulsory question, worth 40 marks, covering the whole module.
  • Four optional questions, worth 20 marks each, and covering different parts of the module. You choose three of them. The four topics in the optional questions are Machine Structure, Bytecode, Invariants and (one combined topic) Operating Systems and Networks.

You can access previous exam papers, including solutions and feedback on last year's (2011-12). Last year's is the most relevant for revising, but note that it had a slightly different format and did not cover Operating Systems and Networks.

Resit exam

There is one resit opportunity for this module in August. It contributes 100% to the module mark -- the exercise mark will not be carried forward.

Textbooks

Goldschlager and Lister: Computer Science: a Modern Introduction (Prentice Hall, 2nd edition 1988)
Some of the module material is derived from this. Despite its age, it is an excellent reference for most of the module.

Reynolds and Tymann: Principles of Computer Science (Schaum's Outlines, McGraw-Hill 2008)
Cheap and useful coverage of many of the module topics.

Lindholm, Yellin, Bracha, Buckley: Java Virtual Machine Specification, Java SE 7 Edition (Oracle) (download or view on-line)
You will not want to read this through, but you will need it for reference - especially the list of instructions in chapter 6.

Broda, Eisenbach, Koshnevissan and Vickers: Reasoned Programming (Prentice Hall, 1994). (Downloadable version here.)
Recommended treatment for weeks 8 and 9.