CS208 - Logic & Algorithms
TIMETABLE | TEACHING MATERIAL |
Credits | 20 |
Level | 2 |
Semester | Semester 1, Semester 2 |
Availability | Not available as an elective |
Prerequisites | CS103 - Machines, Language & Computation and CS105 - Programming Foundations Useful: CS207 - Advanced Programming |
Learning Activities Breakdown | Lectures: 44 | Tutorials: 20 | Assignments: 58 | Self study: 78 |
Items of Assessment | 4 |
Assessment | The class will be assessed 30% by coursework and 70% by a two-hour examination. Coursework assessment details are to be determined by the lecturers: regular assignments, class tests as appropriate, exemptions (if offered) in accordance with standard policy. |
Lecturer | Damien Anderson, Robert Atkey |
Aims and Objectives
To equip students with the tools to model and measure computation. To build on CS103 Machines, Languages and Computation and develop further understanding of the mathematical foundations of computation. To foster an analytical and empirical appreciation of the behaviour of algorithms and the use of abstract data types.
Learning Outcomes
On completion of the class, a student should be able:
- to understand a mathematical basis for a simple natural deduction system and perform rigorous proof construction given a well-defined framework
- to work confidently with propositional logic in a natural deduction setting and develop an understanding of predicate logic
- to understand the concept of an interpreted formal system, along with the concepts of soundness and completeness in this context
- to have a good understanding of the Church-Turing thesis and the general concept of computation, making correlations between different models of computation, e.g., lambda calculus, Turing machines, Hoare’s IMP
- to appreciate the concepts of logical invariant, precondition and postcondition, with respect to data structures and algorithms
- to study a number of fundamental algorithms, including in particular the fundamental algorithms of searching and sorting, identifying the invariants on which they rely
- to make a critical assessment of different implementations of algorithms and abstract data types
- to carry out a number of empirical studies of the performance of algorithms and abstract data types
- to appreciate a number of fundamental computational problems, and be aware of real world instances of those problems
Syllabus
First Semester (items marked with * may be dropped if there is a lack of time):
- Propositional Logic revisited: natural deduction systems; translation between real and formal domains; inference, proofs, axioms; equivalence of systems
- Formal Systems and Interpreted Formal Systems: language, inference and interpretation, syntax and semantics, satisfaction, soundness, completeness
- Predicate Logic: predicates, universal and existential quantification; generalisation, specialisation by symbolic substitution; awareness of free variables, bound variables, and alpha-equivalence
- Relations: relations as predicates, relations as graphs; equivalence relations, preorders, partial orders; functions and partial functions as special cases of relations; simple logic (Prolog) programming as proof search(*)
- Models of Computation: simple abstract machines, Turing machines, expression evaluation, lambda-calculus reduction(*), imperative execution(*), correspondence between models of equivalent strength(*), the Church-Turing thesis
Second Semester:
- Abstract Data Types: Lists, Stacks, Queues, Sets, Trees, Graphs, Maps, Collections, Generics, Iterators.
- Algorithms: Searching and Sorting. Graph Traversal Algorithms.
- Efficiency and Complexity of Algorithms and Data Structures: Big-O Complexity and Asymptotic Analysis.
- Additional Problems, Algorithms and Techniques: as selected by class lecturers
Recommended Reading
This list is indicative only – the class lecturer may recommend alternative reading material. Please do not purchase any of the reading material listed below until you have confirmed with the class lecturer that it will be used for this class.
Logic in Computer Science, 2nd edition Michael Huth and Mark Ryan, Cambridge University Press, 2004, ISBN 978-0-521-54310-1.
Data Structures and Algorithm Analysis in Java, 2nd edition Mark Allen Weiss, Addison-Wesley, ISBN 2007, ISBN 0-321-37013-9.
Algorithm Design: Foundations, Analysis, and Internet Examples Michael T. Goodrich and Roberto Tamassia, John Wiley & Sons, Inc., 2002, ISBN: 0-471-38365-1.
Last updated: 2024-12-03 08:27:33