CS208 - Logic & Algorithms

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:

• Algorithms: algorithms and processes; iteration and recursion, studied comparatively; preconditions, postconditions, and invariants; specification as relation between inputs and outputs
• Introduction to Algorithmic Complexity: basic algorithmic classification, with examples; the order notation (Big-oh); elementary complexity and estimation of run times; the tyranny of growth
• Searching and Sorting: the complexity of a range of techniques, including the divide and conquer approach; the relative complexity of searching and sorting algorithms; the sorting algorithms covered will include bubble sort, insertion sort, merge sort and quick sort; searching, including sequential search and the binary chop; hashing
• Binary Trees revisited: implementations by array and by nodes with pointers; expression trees; binary tree implementation of sorted list; algorithms covered include traversal, searching, balancing and deletion; awareness of ordering and balancing invariants and their implications for correctness and complexity
• Graphs revisited: directed and undirected graphs; representations of graphs; basic graph algorithms; topological sorting; applications of graphs to real world problems (for example telecommunications, transportation systems, dependencies between objects)
• Complexity Implications of ADT Implementation: e.g. for priority queues, graphs; access times
• Fundamental Techniques: divide and conquer, greedy algorithms, dynamic programming, backtracking search
• Additional Problems, Algorithms and Techniques: as selected by class lecturers
• Practical Work: Further exploration of algorithms and abstract data types, empirical evaluation of performance, one or two larger scale exercises.

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-08-19 13:32:34