# Fundamentals of Computing: Introduction to Computer Science

Lecturer: Steve Vickers

This is an emergency page while access via Canvas is being sorted out. Slides after week 1 are old and are all likely to be changed.

This page covers two modules, each compulsory in its degree programme:

For more details see:

## 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: The basic operations, and what can be stored. Slides.
3. CPUs and stored programs: The CPUs that control an computer, and how they interact with memory to execute programs stored in memory. The fetch-execute cycle, and algorithmic structure using jumps. Slides.
4. Subroutines and stacks: How subroutine (method) calls are implemented using stacks; other calculations using stacks. Slides.
5. Java bytecode: The difference between high and low level programming. Illustrated using Java and the Java virtual machine (JVM) and its bytecode. Slides. You can also refer to the Java Virtual Machine Specification.
6. Continuation of Java bytecode, and then Objects: How the JVM deals with objects. Objects and the heap; non-static methods and constructors. Slides.
7. Continuation of Objects.
8. Instance invariants: Logical conditions on the fields of objects that are kept true. 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.
Slides; also some sample source code files: Date, Customer and BankAccount (illustrating instance invariants)
9. Loop invariants: Logical conditions on local variables that are kept true while a loop iterates. Loop invariants are a central tool in planning and debugging iterative algorithms. Binary Search: a very good illustration of the effectiveness of loop invariants.
Slides; also some sample source code files: Sum (simple example of loop invariant), binary search.
Loop invariants and binary search are covered in chapters 10 and 11 of Reasoned Programming.
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:
12. Operating systems (no longer in module): What they do, including memory management and multiprocessing. Slides. See Reynolds and Tymann chapter 6.
13. Networks (no longer in module): Basic principles. Slides. See Reynolds and Tymann chapter 7.

## Timetable

The teaching consists of two lectures each week:

Tuesday 15:00-15:50, Vaughan Jeffries lecture theatre, Education (R19)
Friday 16:00-16.50, in various rooms:

• weeks 1-8: WG5, Aston Webb building (R4)
• weeks 9-10: 124, Chemical Engineering (Y11)
• week 11: LT2, Gisbert Kapp (G8)

(You may want to consult the campus map. R19 and G8 are about 10 minutes from CS, so don't dawdle.)

My office hours are: Tuesdays 16:00-16:50 and Fridays 11:00-11:50, in room 215 CS, and I am available then for drop-in consultation.

## Continuous assessment

The module is assessed 20% by coursework (continuous assessment). There are three pieces of continuous assessment.

Coursework submission, marks, and feedback will be through Canvas.

1. Due for submission by 12.00, Friday 10th October. Worth 3%.
2. Due for submission by 12.00, Friday 14th November. Worth 9%.
3. Due for submission by 12.00, Friday 12th December. Worth 8%.

If you have a serious reason for not being able to complete any piece of coursework, then see someone from the Welfare Team. (The precise procedure is explained in the Student Handbook.) I will normally follow any recommendation from them.

## Policy on plagiarism

Learning from others is at the heart of academic life, and I would encourage you to discuss the module with each other. However, the key word is learning.

When you come to submit work for assessment, it must be something you have formulated by yourself, something you have genuinely learnt.

If you submit work that is largely copied from others, without going properly through your own brain, then there are two issues.

1. The coursework is part of the teaching structure of the module, designed to help you learn the material and provide an opportunity to test out your understanding. If you don't do that conscientiously then you miss that part of the teaching and the exam will come as much more of a struggle.
2. Passing someone else's work off as your own (plagiarism) is academically dishonest and subject to academic discipline.

If I find evidence of plagiarism then I 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.

## 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.

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 8 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.