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:  NormalDay 
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 
PreRequisites:  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. Cstyle languages). The expressive power, and limitations, of different Automata is explored (e.g. Regular, ContextFree, and Recursivelyenumerable 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 OutcomesAssessment Methods: 


Assessment Description: 
Weekly inclass exercises: short exercises to do inclass 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, paperbased 

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 inhouse 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/studentpolicies/ 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 Nondeterminsitic Finite Automata 
Week 6  DFA minimisation, Regular expressions 
Assessment Due: Assignment 1  
Week 7  Contextfree Languages, Grammars 
Week 8  Parsing 
Week 9 
Parsing (revisions) Turing machines, ChurchTuring 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.