Computer Science core 1

In the first year of the Computer Science degree you will begin by studying the basics of Computer Science, starting with how to write a good computer program. Though you may have written programs as part of an A-level in IT at school, you will find that the approach we take to programming is quite different, because the emphasis is on explaining - often using mathematics - why it is that programs work correctly.

Functional Programming

This is a first course in programming. You will use of a programming language called Haskell, which allows programs to be viewed as mathematical functions. This makes the language very powerful, so that we can easily construct programs that would be difficult or very large in other languages. An important theme of the course is how to apply mathematical reasoning to programs, so as to prove that a program performs its task correctly, or to derive it by algebraic manipulation from a simpler but less efficient program for the same problem. You gain hands-on experience of programming through two lab exercises: the first one aims to make you acquainted with the mechanics of writing Haskell programs, and the second one tackles a more challenging programming task of simulating the world of an imaginary animal. This demonstration shows you more about this problem.

Design and Analysis of Algorithms

In this course you will learn about the basics of algorithms, the methods of solving problems by computer, and data structures - the means by which information is represented and manipulated inside a computer. Building on the experience with Haskell from Functional Programming, the course covers the principles of algorithm design, analysis of the performance of algorithms, and the fundamental ideas in the design of efficient data structures. The emphasis is on choosing appropriate data structures for a problem domain and designing correct and effective algorithms to operate on these data structures in solving the problem. You will learn to apply these ideas in practice through a lab exercise.

Imperative Programming

In these courses you will apply lessons you learnt in Functional Programming to the design of programs written in a more conventional way. By studying a sequence of programming examples, each a useful software tool in its own right, you will learn to construct programs in a systematic way, structuring them as a collection of modules with well-defined interfaces. These courses also cover informally the method of invariants for understanding and reasoning about programs that contain loops. You will conclude with the study of a larger programming example, such as a graphical program for finding the best route for driving between specified towns in the UK. You can further explore this problem using this demonstration. Through lab exercises, you will learn to create, debug and maintain programs of a non-trivial but moderate size.

The second part of the course introduces the ideas of Object Oriented Programming: abstract data types and data encapsulation; interfaces and polymorphism; and generics and collection classes. In lab sessions, you will work to develop and enhance your own text editor, supporting incremental search and multi-level undo.

Digital Systems

On this course you will learn about the fundamentals of the electronic circuits that are used to build computers. Beginning with the functions of individual transistors, and building towards a complete implementation of a simple processor, the course explains in a structured way how complex behaviours are built up from simpler parts. You will gain an understanding of the factors that affect the performance of hardware, and how these factors alter with changes of scale, for example in the size of the data that a computer system handles.

Linear Algebra

Another important application of computers in Mathematics is in solving problems that can be expressed as systems of simultaneous linear equations. You will have learnt at school how to solve particular sets of simultaneous equations, but this course goes further. You will study the general conditions that determine which systems of equations have solutions, and for which systems the solution is unique, as well as systematic methods for solving systems of equations. This demonstration which you might program during your 2nd year utilizes the mathematics you will learn in this course along with the 2nd year numerical computation course.

Continuous Mathematics

This will be taught by the Department of Computer Science. Many areas of mathematics, and applications of mathematics in the applied sciences, are underpinned by the concepts of calculus, i.e. differentiation and integration. The first aim of this course is to provide an introduction to calculus in several variables that will form a basis for later courses. This theory will be demonstrated using examples drawn from maximising or minimising functions of one or more variables, the solution of ordinary differential equations, and the solution of simple partial differential equations (including the reduction of partial differential equations to ordinary differential equations via a change of variables in special cases). The second aim of the course is to introduce some computational techniques in calculus, for example numerical integration and the numerical solution of differential equations. These techniques lend themselves to practical implementation, allowing demonstration of the theory developed during the course.

Discrete Mathematics

This course will provide you with the vocabulary of concepts that is needed to understand in mathematical terms the problems that computer systems are designed to solve, and to analyse proposed solutions for their correctness and efficiency. Specifications of computer systems can be expressed formally in terms of sets, relations and functions, and the correctness of programs that implement these specifications is often proved using the techniques of mathematical logic, including reasoning based on mathematical induction. This reasoning may involve the mathematical properties of permutations, orderings, and other similar concepts. Finally, analysis of the efficiency of programs may involve solution of recurrence relations, combinatorial calculations, and the use of asymptotic approximations. All these ideas will be introduced to you in this course.

Introduction to Proof Systems

The course is an introduction to logic and proof systems. You will develop skills of using formal logic to express and prove useful properties of mathematical structures and more generally in constructing rigorous proofs and manipulating formal notation. You will be exposed to basic logic topics, including proof systems, resolution, satisfiability, compactness, Skolemisation, and Herbrand models.

Probability

This course introduces some concepts from probability theory. You will learn about random processes, and learn to understand and apply probabilistic models such as the Binomial and Poisson distributions. Probability is useful in Computer Science not only to answer questions about the average performance that can be expected of computer systems, but also in advanced topics like Randomised Algorithms, in which some otherwise 'hard' problems can be solved faster using a program that makes random choices.