CA215 Languages & Computability

NB, Tutorials begin Monday 15th October.

Course Rationale

The aims of this module are:

To give students a grounding in formal language theory.
To give students a grounding in the theory of computation.
To study the relationships between languages, computational models and computational problems.

A nice summary of what the course is about is:

"Computer Science is no more about computers than astronomy is about telescopes", by Edsger Dijkstra.

Lectures

The course is divided into two parts:

Computability Theory, which will be taught by:
- Andy Way, Jie Jiang and Özlem Çetinoģlu on Mondays at 14:00 in C104;
- Sergio Penkale and Yifan He on Mondays at 16:00 in XG14, and 17:00 in X130;
Functional Programming, which will be taught by:
- Sara Morrissey and Jinhua Du on Thursdays at 10:00 in CG05.
- Sara Morrissey, Jinhua Du and Ankit Srivastava on Fridays from 9:00 -- 11:00 in LG25 & LG26.

You can contact me at away at-thing computing.dcu.ie, or by phone on 5644, or in person in room L201C.

We're all located in the CNGL on the top floor of the older School of Computing building, in L201. If you can't get past the swipe card system, contact Eithne McCann, the CNGL Secretary, who's in L217, and she'll let you in.

Assessment

The course is assessed by one programming exam worth 25%, and an end-of-semester exam worth 75%. Given the new academic regulations, the course can be passed by failing the labtest or the exam as long as the overall mark for the whole course is 40%.

Indicative Syllabus

The indicative syllabus from the module spec. includes the following topics:

Mathematical Prerequisites
- sets
- cardinality and countability
- functions
- relations
- induction and recursion
languages and grammars
models of computation
- definition of Turing machines
- Turing machines as language acceptors
- computing with Turing machines
- extensions of Turing machines
- non-deterministic Turing machines
Recursively Enumerable and Recursive Languages
- recursively enumerable
- recursive
Unsolvable Problems

We'll see what of this we manage to cover in practice (and in what order) as we go along.

Course Notes

Thanks to the previous custodian of this course, Geoff Hamilton, an excellent set of notes already exists for this course. I'll add to this if and when necessary, and may on occasion depart from what Geoff has provided, but I think it's sufficient at least at this early stage to make Geoff's notes available pretty much 'as is' here:

Jie Jiang's Computability notes are available here:

Özlem Çetinoģlu's notes are available on her webpage.

Sara Morrissey and Jinhua Du have made Haskell slides available.

Useful Texts

Elements of the Theory of Computation, H.R. Lewis & C.H. Papadimitriou, Prentice Hall, 1998 (2nd edition), [511.3/LEW]
Theory of Computing, E. Kinber & C. Smith, Prentice Hall, 2001 [004/KIN]
Haskell: The Craft of Functional Programming, S. Thompson, Addison Wesley, 1999 (2nd edition), [005.133/THO]

Past Exam Papers

In case students have difficulties accessing the copies kept by the Registry, here are previous exam papers, starting with academic year 2006--07, which was when I began teaching this course:

As you can see, each exam comprises 5 questions, with a free choice of any three questions to be completed.

Other DCU-internal Information

The official DCU page for this module gives basic information pertaining to this course. There is a separate DCU page entitled Module Resources which may also be useful.

17th November, 2009