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, which include some of the greatest intellectual advances of the last century: 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 the finite automata introduced in earlier years, and then generalise to pushdown automata, and show that they have more power. Next we generalize further to very simple abstract general computers, and argue they can do everything real computers can do. We then ask, can we solve every computational question? The answer, with which Turing shocked the mathematicians of the 1930s, is "no", with a remarkably easy but beautiful argument (introduced at the end of Inf2IADS INFR08026). 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 Inf2IADS INFR08026 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 problemsolving 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 takes brief look at 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 lambdacalculus (on which Haskell is based) can do all the computing our other models could, and how the halting problem was actually first solved (or rather unsolved) within lambdacalculus.

Entry Requirements (not applicable to Visiting Students)
Prerequisites 

Corequisites  
Prohibited Combinations  
Other requirements  This course is open to all Informatics students including those on joint degrees. It is also open to students in the School of Mathematics. 
Information for Visiting Students
Prerequisites  None 
High Demand Course? 
Yes 
Course Delivery Information

Academic year 2024/25, Available to all students (SV1)

Quota: None 
Course Start 
Semester 1 
Timetable 
Timetable 
Learning and Teaching activities (Further Info) 
Total Hours:
100
(
Programme Level Learning and Teaching Hours 2,
Directed Learning and Independent Learning Hours
98 )

Assessment (Further Info) 
Written Exam
80 %,
Coursework
20 %,
Practical Exam
0 %

Additional Information (Assessment) 
An 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, the first coursework being formative and the second being summative. Additional formative work in tutorial sheets will stretch those who wish.
You should expect to spend approximately 15 hours on the coursework for this course. 
Feedback 
Formative feedback is given verbally in tutorials, and in writing for the first exercise. Summative and formative feedback is given in writing for the second exercise. 
Exam Information 
Exam Diet 
Paper Name 
Hours & Minutes 

Main Exam Diet S1 (December)  Introduction to Theoretical Computer Science (INFR10059)  2:120   Resit Exam Diet (August)   2:00  
Learning Outcomes
On completion of this course, the student will be able to:
 explain (non)deterministic finite and pushdown automata and use the pumping lemma to show languages nonregular
 explain decidability, undecidability and the halting problem
 use reductions to show (un)decidability
 explain P and NP and use reductions to show (non)membership of them
 write short programs in lambdacalculus

Reading List
Michael Sipser, Introduction to the Theory of Computation.
Benjamin Pierce, Types and Programming Languages. 
Additional Information
Course URL 
https://opencourse.inf.ed.ac.uk/itcs 
Graduate Attributes and Skills 
Problemsolving, analytical thinking, mathematical communication 
Keywords  Computability,Complexity 
Contacts
Course organiser  Prof Philip Wadler
Tel: (0131 6)50 5174
Email: philip.wadler@ed.ac.uk 
Course secretary  Miss Rose Hynd
Tel: (0131 6)50 5194
Email: rhynd@ed.ac.uk 

