Note: This unit version is currently being edited and is subject to change!

COMP2022: Programming Languages, Logic and Models (2019 - Semester 2)

Download UoS Outline

Unit: COMP2022: Models of Computation (6 CP)
Mode: Normal-Day
On Offer: Yes
Level: Intermediate
Faculty/School: School of Computer Science
Unit Coordinator/s: Godbehere, Joseph William
A/Prof Yacef, Kalina
Session options: Semester 2
Versions for this Unit:
Site(s) for this Unit:
Campus: Camperdown/Darlington
Pre-Requisites: INFO1103 OR INFO1113 OR INFO1903.
Prohibitions: COMP2922.
Brief Handbook Description: This unit provides an introduction to the foundations of computational models - including Lambda Calculus (functional approach), Automata Theory (stateful approach), and Logic calculi (propositional and predicate logic, formal proofs). Practical use is illustrated by exploring programming languages based upon them, i.e. functional programming (e.g. Haskell) and logic programming, in contrast to the procedural languages most students will already be familiar with (e.g. C-style languages). The expressive power, and limitations, of different Automata is explored (e.g. Regular, Context-Free, and Recursively-enumerable languages), culminating with Turing machines and the notions of computability and decidability.
Assumed Knowledge: MATH1004 OR MATH1904 OR MATH1064 OR MATH2069 OR MATH2969.
Additional Notes: From 2020, this unit will be renamed to Models of Computation.
Lecturer/s: Godbehere, Joseph William
A/Prof Yacef, Kalina
Timetable: COMP2022 Timetable
Time Commitment:
# Activity Name Hours per Week Sessions per Week Weeks per Semester
1 Lecture 2.00 1 13
2 Tutorial 2.00 1 13
3 Independent Study 8.00 1 13
T&L Activities: Independent Study: Students are expected to undertake the prescribed reading and work on homework exercises and assignments.

Learning outcomes are the key abilities and knowledge that will be assessed in this unit. They are listed according to the course goal supported by each. See Assessment Tab for details how each outcome is assessed.

Unassigned Outcomes
1. Knowledge of basic discrete maths, theorems and formal proofs
2. Understanding of lambda calculus
3. Understanding of Propositional Logic
4. Understanding of Predicate Logic
5. Ability to use Languages/Tools for Propositional Logic
6. Understanding of Functional Programming concepts
7. Awareness of the Chomsky hierarchy, Turing machines, and the notions of decidability and intractability.
8. Understanding of the concept of propositional and first order logic as a model of facts and of reasoning.
9. Understanding of the concept of formal language as a set of strings, and of operations on formal languages, in particular union, concatenation, and Kleene closure.
10. Ability to use regular languages and their representations by DFAs, NFAs, regular expressions, and regular grammars.
11. Ability to use context-free grammar as a model of formal language.
Assessment Methods:
# Name Group Weight Due Week Outcomes
1 Weekly exercises No 9.00 Multiple Weeks 1, 2, 3, 4, 6, 7, 8, 9, 10, 11,
2 Assignment 1 No 10.00 Week 6 1, 2, 6, 10,
3 Assignment 2 No 16.00 Week 10 1, 9, 11,
4 Assignment 3 Yes 5.00 Week 12 1, 3, 5, 8,
5 Final exam No 60.00 Exam Period 1, 2, 3, 4, 6, 7, 8, 9, 10, 11,
Assessment Description: Weekly in-class exercises: short exercises to do in-class at the beginning of each tutorial.

Assignments: the first 2 are individual assignments, which consist of a report and a programming part. The 3rd assignment is a formal proof, to be done individually or in pairs.

Final Exam: 2 hour exam, paper-based
Assessment Feedback: Assignments are handed back within 2 weeks with written feedback. General feedback given in the lecture or in the tutorial.

Solutions of tutorials are posted each week.
Grading:
Grade Type Description
Standards Based Assessment Final grades in this unit are awarded at levels of HD for High Distinction, DI (previously D) for Distinction, CR for Credit, PS (previously P) for Pass and FA (previously F) for Fail as defined by University of Sydney Assessment Policy. Details of the Assessment Policy are available on the Policies website at http://sydney.edu.au/policies . Standards for grades in individual assessment tasks and the summative method for obtaining a final mark in the unit will be set out in a marking guide supplied by the unit coordinator.
Minimum Pass Requirement It is a policy of the School of Computer Science that in order to pass this unit, a student must achieve at least 40% in the written examination. For subjects without a final exam, the 40% minimum requirement applies to the corresponding major assessment component specified by the lecturer. A student must also achieve an overall final mark of 50 or more. Any student not meeting these requirements may be given a maximum final mark of no more than 45 regardless of their average.
Policies & Procedures: IMPORTANT: School policy relating to Academic Dishonesty and Plagiarism.

In assessing a piece of submitted work, the School of Computer Science may reproduce it entirely, may provide a copy to another member of faculty, and/or to an external plagiarism checking service or in-house computer program and may also maintain a copy of the assignment for future checking purposes and/or allow an external service to do so.

Other policies

See the policies page of the faculty website at http://sydney.edu.au/engineering/student-policies/ for information regarding university policies and local provisions and procedures within the Faculty of Engineering and Information Technologies.
Recommended Reference/s: Note: References are provided for guidance purposes only. Students are advised to consult these books in the university library. Purchase is not required.
Online Course Content: USyd Canvas

Note that the "Weeks" referred to in this Schedule are those of the official university semester calendar https://web.timetable.usyd.edu.au/calendar.jsp

Week Description
Week 1 Unit Introduction, Introduction to computational models
Week 2 Lambda Calculus / Functional Programming 1
Week 3 Lambda Calculus / Functional Programming 2
Week 4 Lambda Calculus / Functional Programming 3
Week 5 Regular Languages, Deterministic and Non-determinsitic Finite Automata
Week 6 DFA minimisation, Regular expressions
Assessment Due: Assignment 1
Week 7 Context-free Languages, Grammars
Week 8 Parsing
Week 9 Parsing (revisions)

Turing machines, Church-Turing hypothesis, Notion of decidability and tractability
Week 10 Propositional logic, Formal proofs
Assessment Due: Assignment 2
Week 11 Formal proofs (cont), Tautologies, proving invalidity

Introduction to Predicate Logic (1)
Week 12 Predicate Logic, formal proofs
Assessment Due: Assignment 3
Week 13 Revisions, Final exam matters
Exam Period Assessment Due: Final exam

Course Relations

The following is a list of courses which have added this Unit to their structure.

Course Year(s) Offered
Bachelor of Advanced Computing (Computer Science Major) 2018, 2019, 2020
Bachelor of Information Technology/Bachelor of Arts 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Commerce 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Medical Science 2015, 2016, 2017
Bachelor of Information Technology/Bachelor of Science 2015, 2016, 2017
Information Technology (Computer Science) / Commerce 2013, 2014
Information Technology (Computer Science) / Medical Science 2013, 2014
Bachelor of Information Technology/Bachelor of Laws 2017, 2015, 2016
Bachelor of Advanced Computing/Bachelor of Commerce 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Health) 2018, 2019, 2020
Bachelor of Advanced Computing/Bachelor of Science (Medical Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Computational Data Science) 2018, 2019, 2020
Bachelor of Advanced Computing (Information Systems Major) 2018, 2019, 2020
Bachelor of Advanced Computing (Software Development) 2018, 2019, 2020
Bachelor of Computer Science and Technology 2015, 2016, 2017
Bachelor of Computer Science and Technology (Advanced) 2015, 2016, 2017
Bachelor of Computer Science and Technology (Computer Science) 2014 and earlier 2013, 2014
Bachelor of Computer Science and Technology (Computer Science)(Advanced) 2014 and earlier 2013, 2014
Bachelor of Computer Science and Technology (Information Systems) 2014 and earlier 2013, 2014
Bachelor of Computer Science and Technology (Information Systems)(Advanced) 2014 and earlier 2013, 2014
Bachelor of Computer Science & Tech. Mid-Year 2016, 2017
Aeronautical Engineering / Science 2014
Aeronautical Engineering (Space) / Science 2014
Biomedical Engineering / Science 2014
Chemical & Biomolecular Engineering / Science 2014
Civil Engineering / Science 2014
Electrical Engineering / Science 2014
Electrical Engineering (Computer) / Science 2014
Electrical Engineering (Power) / Science 2014
Electrical Engineering (Telecommunications) / Science 2014
Aeronautical / Science 2015, 2016, 2017
Aeronautical (Space) / Science 2015
Biomedical Mid-Year 2016, 2017, 2018, 2019, 2020
Biomedical 2016, 2017, 2018, 2019, 2020
Biomedical /Science 2015, 2016, 2017
Chemical & Biomolecular / Science 2015
Civil / Science 2015
Electrical / Science 2015
Electrical (Computer) / Science 2015
Electrical (Power) / Science 2015
Electrical (Telecommunications) / Science 2015
Mechanical / Science 2015, 2016, 2017
Mechanical (Space) / Science 2015
Mechatronic / Science 2015, 2016, 2017
Mechatronic (Space) / Science 2015
Software Mid-Year 2016, 2017, 2018, 2019, 2020
Software 2015, 2016, 2017, 2018, 2019, 2020
Mechanical Engineering / Science 2014
Mechanical Engineering (Space) / Science 2014
Mechatronic Engineering / Science 2014
Mechatronic Engineering (Space) / Science 2014
Software Engineering / Science 2014
Bachelor of Information Technology 2015, 2016, 2017
Bachelor of Information Technology (Computer Science) 2014 and earlier 2013, 2014
Information Technology (Computer Science)/Arts 2013, 2014
Information Technology (Computer Science) / Science 2013, 2014
Information Technology (Computer Science) / Law 2013, 2014
Bachelor of Information Technology (Information Systems) 2014 and earlier 2013, 2014
Information Technology (Information Systems)/Arts 2013, 2014
Bachelor of Project Management (Built Environment) 2018, 2016, 2017
Bachelor of Project Management (Civil Engineering Science) 2018, 2016, 2017
Bachelor of Project Management (Software) 2018, 2016, 2017
Bachelor of Project Management (Built Environment) Mid-Year 2016, 2017, 2018
Bachelor of Project Management (Civil Engineering Science) Mid-Year 2016, 2017, 2018
Bachelor of Project Management (Software) Mid-Year 2016, 2017, 2018

Course Goals

This unit contributes to the achievement of the following course goals:

Attribute Practiced Assessed
(5) Interdisciplinary, Inclusiveness, Influence (Level 2) No 0%
(4) Design (Level 2) No 0%
(3) Problem Solving and Inventiveness (Level 2) No 0%
(2) Engineering/ IT Specialisation (Level 2) No 0%
(1) Maths/ Science Methods and Tools (Level 2) No 0%

These goals are selected from Engineering & IT Graduate Outcomes Table 2018 which defines overall goals for courses where this unit is primarily offered. See Engineering & IT Graduate Outcomes Table 2018 for details of the attributes and levels to be developed in the course as a whole. Percentage figures alongside each course goal provide a rough indication of their relative weighting in assessment for this unit. Note that not all goals are necessarily part of assessment. Some may be more about practice activity. See Learning outcomes for details of what is assessed in relation to each goal and Assessment for details of how the outcome is assessed. See Attributes for details of practice provided for each goal.