This is an archived syllabus from 2013-2014
COMP11212 Fundamentals of Computation syllabus 2013-2014
COMP11212 Fundamentals of Computation
Enrolled students: 218
Course leader: Andrea Schalk
Additional staff: view all staff
- 75% Written exam
- 25% Coursework
|Sem 2||Lecture||1.1||Wed||09:00 - 09:00||-|
|Sem 2||Lecture||1.1||Thu||10:00 - 10:00||-|
|Sem 2 w2+||Examples||IT407||Mon||13:00 - 13:00||M+W|
|Sem 2 w2+||Examples||IT407||Mon||14:00 - 14:00||B+X|
|Sem 2 w2+||Examples||IT407||Mon||15:00 - 15:00||Y|
|Sem 2 w2+||Examples||IT407||Mon||16:00 - 16:00||Z|
|Sem 2 w27||ADHOCBOOKING||1.1||Fri||17:00 - 17:00||2014/03/26-10:06:44|
The building of real-life computing systems, e.g. mobile phone, tv/video remote control, internet shopping, air-traffic control, internet banking, etc., is always a complex task. Mistakes can be very annoying, costly and sometimes life threatening. Methods and techniques to support the building and understanding of such systems are essential. This course unit provides an introduction to the basic computer science ideas underlying such methods. It is also a part of, and an introduction to, the Modelling and Rigorous Development theme.
This course unit provides a first approach to answering the following questions. What methods are there that can help understanding complicated systems or programs? How can we make sure that a program does what we intend it to do? How do computers go about recognizing pieces of text? If there are two ways of solving the same problem, how can we compare them? How do we measure that one of them gives the solution faster? How can we understand what computers can do in principle, and are there problems that are not solvable by a computer?
There are two groups of topics covered. One of the lectures will be an introduction to the course unit, and one is reserved for revision. That leaves 10 lectures for each part.
The first part (10 lectures) is concerned with expressing particular strings, and collections of strings, and here we will introduce the methods by which a computer goes about it. The ability to recognize key strings (such as programming constructs or variable names) are, for example, required in every compiler, but they are also used by search engines such as Google.The formalisms introduced include finite state automata, regular expressions (most often used in pattern matching), (regular) grammars. The emphasis is on students being able to use these formalisms to solve problems.
The second group (10 lectures) provides anintroduction to the two topics of computability and computational complexity. There are five big topics:
- recursion and induction
- the WHILE programming language
- asymptotic complexity
- partial and full program correctness
22 in total, 2 per week
1 per week (starting in week 2)
Feedback methodsStudents present their solutions to set exercises once a week in examples classes. They receive oral feedback to their solutions, and have the opportunity to improve some of their original answers for further feedback.
- Assessment written exam (2 hours)
- Lectures (24 hours)
- Practical classes & workshops (11 hours)
- Analytical skills
- Oral communication
- Problem solving
On successful completion of this unit, a student will be able to:
Learning outcomes are detailed on the COMP11212 course unit syllabus page on the School of Computer Science's website for current students.
|Introduction to the Theory of Computation||Michael Sipser||113318779X; 9781133187790; 9781133187813||Cengage Learning||2013|
|Logic in computer science : modelling and reasoning about systems||Huth, Michael,||9780511810275||Cambridge University Press||2004.|
|Introduction to automata theory, languages, and computation||Hopcroft, John E., 1939-||9781292056166||Pearson Education||©2014.|
|Introduction to the theory of computation||Sipser, Michael.||9781133187813||Cengage Learning||c2013.|
Course unit materials
Links to course unit teaching materials can be found on the School of Computer Science website for current students.