Steve Vickers: Introduction to Computer Science

Solutions and feedback on coursework 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.

The lectures will often not be pre-prepared slides, so you will have to attend and take notes. However, for convenience, last years slides are available. (Thanks to Behzad Bordbar, Ata Kaban and Guilin Wang.)

  1. Introduction and Turtles: You will want to try my turtle graphics package. It provides a simple introduction to some of the algorithmic structure that we shall look at in week 2.
  2. Algorithmic structure: Sequencing, selection, repetition (iteration) and modules (subroutines, methods). There were no slides this week. A detailed example on planning a repetitive algorithm used binary search. This is exactly the algorithm you use when you look up a word in a dictionary, relying on the fact that it is in alphabetical order. The planning technique, using "loop invariants", is covered more fully in week 9.
  3. Memory: What memory does and why there are different kinds. Slides.
  4. CPUs: The logical structure of CPUs, the operations they can perform, and how they interact with memory. Slides.
  5. More on CPUs: Stored programs, the fetch-execute cycle, algorithmic structure using jumps, stacks and the difference between high and low level programming. The same slides as last week.
  6. Numbers: Number bases, binary, octal, hex; also floating point. Slides.
  7. Java bytecode: The Java virtual machine (JVM) and its bytecode. Slides. You can also download the Java Virtual Machine Specification.
  8. Objects: Objects and the heap; non-static methods and constructors. Slides; also some sample source code files Factorial, TempC and TempCF and disassembled bytecode.
  9. 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: 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.
  10. Recursion: Methods that call themselves, either directly or indirectly.
    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. See also chapter 3 of Goldschlager and Lister.
    You may also enjoy Geoffrey Pullum's poem "Scooping the Loop Snooper", about the Halting Problem, and Richard Kaye's Minesweeper Pages, about NP-completeness of the Minesweeper Consistency Problem. If you solve the "P = NP?" problem and wish to claim your million dollar prize, check the Clay Mathematics Institute website.

    12. Revision

    Be guided by the coursework exercise. It was designed to prepare you for the exam questions. If you are on the intercalated year and have not looked at the exercise, do so now as part of your revision. If you did the exercise and got lower marks than you hoped, make sure you understand the key ideas that the exercises were about - for example, how invariants are used, basic working of bytecode. See also the solutions and feedback.

    There are differences between the way an exam question is set and the way assessed coursework is set. Since you aren't able to use reference books in the exam, the questions will often remind you of necessary information. For example, the paper will list the meanings of a range of bytecode instructions.

    As you can see from the description of the exam, you answer a compulsory question and 2 out of 3 optional ones.

    The compulsory question consists of small parts covering the whole module.

    The optional questions go deeper and each is based on a substantial topic of the course.
    The assessed exercise indicates two of those substantial topics:

    • invariants
    • understanding bytecode

    There is another substantial topic that was not covered so much in the exercise:

    • operation of CPU and memory

    Timetable

    The teaching consists of two lectures each week, both on Tuesdays:
    9:00--9:50am, Room LG32 Learning Centre (Building R28)
    4:00--4:50pm, Room E102 Biosciences (Building R27)

    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 is one piece of continuous assessment and it contributes 10% to the module mark. It consists of an exercise on invariants and Java bytecode to be done over the Christmas vacation.

    The Java code for question 1 and solutions are now available. You are strongly recommended to read the feedback on general performance, especially if you got less than 24/40 for the coursework. It gives hints for how to prepare better for the exam.

    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.
    • Three optional questions, worth 30 marks each, and covering different parts of the module. You choose two of them.

    Here are past exam papers. Those for 2006-9 cover two different modules; the questions for Introduction to Computer Science are the first section only.

    The past papers are not very similar to this year's, since the module content has changed quite a lot. See the revision notes.

    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.

    Broda, Eisenbach, Koshnevissan and Vickers: Reasoned Programming (Prentice Hall, 1994). (Downloadable version here.)
    Recommended treatment of some of the first part of the module.