Note: This unit version is currently being edited and is subject to change!
COMP2922: Programming Languages, Logic and Models (Adv) (2019 - Semester 2)
| Unit: | COMP2922: Models of Computation (Adv) (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: | INFO1113 OR INFO1103 OR INFO1903. Distinction level result in the above 1000 level units. |
| Prohibitions: | COMP2022. |
| 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 (e.g. Prolog), 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) AND (INFO1105 OR INFO1905 OR COMP2123 OR COMP2823). |
| Additional Notes: | From 2020, this unit will be renamed to Models of Computation (Adv). |
| Lecturer/s: |
Godbehere, Joseph William
A/Prof Yacef, Kalina |
||||||||||||||||||||
| Timetable: | COMP2922 Timetable | ||||||||||||||||||||
| Time Commitment: |
|
||||||||||||||||||||
| 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: |
|
||||||||||||||||||||||||||||||||||||
| 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: |
|
||||||||||||||||||||||||||||||||||||
| 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 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.
