Undergraduate Course: Introduction to Theoretical Computer Science (INFR10059)
Course Outline
| School | School of Informatics |
College | College of Science and Engineering |
| Credit level (Normal year taken) | SCQF Level 10 (Year 3 Undergraduate) |
Availability | Available to all students |
| SCQF Credits | 10 |
ECTS Credits | 5 |
| Summary | This course introduces the fundamental concepts of the theory of computer science: what does `computing' mean? Are all `computers' basically the same? Can we tell whether our programs are `correct' - and what does `correct' mean, anyway? Can we solve problems in reasonable time, and can we tell whether we can?
The course concentrates primarily on conceptual understanding, but adds enough detail to allow students to go on to further courses, and illustrates how the fundamental concepts are reflected throughout the discipline.
|
| Course description |
The first section of the course asks the question, what does it mean to compute? We start with very simple abstract computers, and argue they can do everything real computers can do. We then ask, can we solve every computational question? The answer, which which Turing shocked the mathematicians of the 1930s, is "no", with a remarkably easy but beautiful argument (introduced at the end of Inf2A). We then explore some different, but always equivalent, ways of defining "a computer". We finish the section by asking how we can compare the difficulty of different problems, and introduce the idea of "reduction" as a way of compiling one problem into another. Technically, this covers register machines, undecidability, Turing machines, and reductions.
The second section thinks about how hard it is to solve solvable problems, leading to one of the most important problems in all mathematics, and the foundation of internet security. We start by reprising Inf2A analysis of algorithms, and then discuss the idea of classifying problems as `tractable' (easy) or `intractable' (hard). We find that the idea of algorithms whose running time grows polynomially in the problem size is a good mathematical definition of `tractable', though not always a practical one. After making this more precise, we ask what happens if we're allowed to just check all the possible answers in parallel - does this give us more problem-solving power? The question is made precise by the concept of NP, and we show that there are "hardest" such problems, such as the famous Travelling Salesman. Although the question is easy to ask, nobody knows how to answer it. This is P = NP - if you can solve it, you win a million dollars, and fame for as long as civilization lasts. So far, NP problems are very hard to solve in practice, so we discuss how to deal with them. We finish the section by talking about much harder problems still. Technically, this section covers P, NP, hardness and completeness, Cook's Theorem, P = NP, and the complexity hierarchy above NP.
The third section considers a different way of seeing computation. Haskell needn't be seen as a programming language, it can be the computer itself. We'll show how the lambda-calculus (on which Haskell is based) can do all the computing our other models could. Unlike the register and Turing machines, lambda-calculus lets us easily use types, which get rid of a whole class of possible bugs from our programs. This "typing" underlies almost all modern languages, including such recent things as generics in Java. We'll show how we can decide whether a lambda program is correct in its type, and even how we can do the typing automatically, instead of making the programmer do it. It turns out that this latter is one of those weird problems that is ridiculously hard in theory, but perfectly doable in practice, which bring us back to the complexity hierarchies of the second section. Technically, this covers lambda-calculus, simple types, polymorphism, type checking and type inference.
Register and Turing machines, undecidability, reductions. Intractability and growth rates. P and poly-time reductions, NP, hardness and completeness. Cook's Theorem. P = NP. Beyond NP. Lambda-calculus, through to simply-typed lambda, type safety, polymorphism, type inference and Hindley-Milner.
|
Entry Requirements (not applicable to Visiting Students)
| Pre-requisites |
|
Co-requisites | |
| Prohibited Combinations | |
Other requirements | This course is open to all Informatics students including those on joint degrees. For external students where this course is not listed in your DPT, please seek special permission from the course organiser. |
Information for Visiting Students
| Pre-requisites | None |
| High Demand Course? |
Yes |
Course Delivery Information
|
| Academic year 2017/18, Available to all students (SV1)
|
Quota: None |
| Course Start |
Semester 2 |
Timetable |
Timetable |
| Learning and Teaching activities (Further Info) |
Total Hours:
100
(
Lecture Hours 20,
Seminar/Tutorial Hours 10,
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
68 )
|
| Assessment (Further Info) |
Written Exam
70 %,
Coursework
30 %,
Practical Exam
0 %
|
| Additional Information (Assessment) |
A written exam provides the main assessment. In order to ensure coverage of the three major sections, the format will be three compulsory easier questions, and a choice of one of two longer questions.
Assessed coursework will be issued at two points, containing mainly relatively straightforward exercises designed to reinforce basics. Formative work in tutorial sheets will stretch those who wish.
You should expect to spend approximately 30 hours on the coursework for this course.
If delivered in semester 1, this course will have an option for semester 1 only visiting undergraduate students, providing assessment prior to the end of the calendar year. |
| Feedback |
Not entered |
| Exam Information |
| Exam Diet |
Paper Name |
Hours & Minutes |
|
| Main Exam Diet S2 (April/May) | | 2:00 | | | Resit Exam Diet (August) | | 2:00 | |
Learning Outcomes
On completion of this course, the student will be able to:
- Explain decidability, undecidability and the halting problem
- Demonstrate the use of reductions for undecidability proofs
- Explain the notions of P, NP, NP-complete , and use reductions to show problems to be NP- hard
- Write short programs in lambda-calculus
- Explain and demonstrate type-inference for simple programs
|
Reading List
Michael Sipser, Introduction to the Theory of Computation.
Benjamin Pierce, Types and Programming Languages.
|
Contacts
| Course organiser | Dr Julian Bradfield
Tel: (0131 6)50 5998
Email: |
Course secretary | Mrs Victoria Swann
Tel: (0131 6)51 7607
Email: |
|
© Copyright 2017 The University of Edinburgh - 6 February 2017 8:08 pm
|
University Homepage