FIT2014 is core in BCS, BSE, BCS/BA, BCS/LLB, and BSc/BCS, and is a core in a computer science major in BSc. It was introduced as part of the 2006 Faculty restructure and will be part of the revised degree roll out of level 2 units for 2007. Previously these degrees had a core unit CSE2303. FIT2014 is based on CSE2303 Formal Methods I but has been substantially revised due to changes in the pre-requisite units and other core units in the degrees.

06/07/2021: Admin - changing workshops to practical as per email from Academic Workforce.

14/06/2021: CE (Graham Farr): clarification: the extra hour of lectures per week is not for new content; about half of it will be used for extended explanation of existing content and some unexaminable historical background; the other half will be workshops and activities designed for consolidation, enrichment, and practice. The simplified description "three lectures per week" is to specify the timetabling need.

07/06/2021: CE (Graham Farr): change from two lectures per week to three lectures per week (with corresponding adjustments), following wide consultation. Reasons: to cover more thoroughly the more challenging parts of the unit; to help students make better use of tutorial time and assignment preparation time; to make more room for some historical material; to make more connections with practice and with relevant historical, social, and philosophical topics; to make more links with research in CS; to restore class contact time to where it should be for this unit and where it already is for comparable units.

18 June 2020: removed hurdle requirement (inconsistent with threshold/competency hurdles)

15 June 2020: modification assessment weighting and learning outcomes to suit online learning and open book exam format

30/03/2020: Admin - submitting changes made to prereqs on 28/10/19.

28 October 2019: Add MTH1035 (advanced version of MTH1030)as an alternate maths prerequisite. Effective S1 2020.

20/9/2019: Admin - updating exam duration to include additional 10 minutes as per University requirement.

29/08/2017 - Admin: update prerequisites to include a new unit being introduced as part of the redevelopment of the Bachelor of Computer Science Advanced (Honours) for 2018.

April 2017. On behalf of CE, updating exam from 70 to 60% as required by revised University Assessment procedures, effective S2 2017. The exam length is to remain as 3 hours. The longer exam is required to fully assess that students have met the learning outcomes, as there are a lot of complex concepts. Students need to demonstrate their ability to use and implement these concepts, and solve complex problems.

October 2016: Add ENG1005 as a possible Maths prerequisite for students doing Eng double degrees. Discussed with CE (Graham Farr).

October 2016: Add "old" prerequisites for students in transition from old course structures.

October 2016: Minor updates to learning outcomes, synopsis, contact hours and prerequisites for 2017 offering. Updates have been discussed with the BCS course director and submitted by the CE (Graham Farr).

October 2016: Admin update to reflect changes approved in 2015 for the 2017 offering.

November 2015: Reverting learning outcomes and synopsis back to 2015 version as revised version of the unit will not be offered until 2017. Amended prerequisites to allow students completing FIT1045 in place of FIT1029 to enrol in the unit.

Oct 2015: Removal of references to logic programming as that has been moved to new unit FIT2102 Programming Paradigms. (It was always an uncomfortable squeeze in FIT2014, with no time to really teach it in lectures.) Make the presence and role of proofs more explicit.

July 2014: Correction of tutorial time - should be 2 hours, was incorrectly entered as 1 when the contact hours were changed to workload requirements.

July 2014: CE changed assessment to include hurdle, revised learning outcomes to be AQF compliant, change of contact person, reduce labs from 3 to 2 hours.

September 2013: Remove transition prerequisite arrangements as these are no longer required.

Removed maths co-requisite requirement - now that MAT2003 has moved to S2 of second year, this is causing progression issues for students. Discussed with CE and BCS course director. Prerequisite of 6 pts maths and FIT1029 is sufficient. For semester 1, 2012 implementation.

Modified Pre-reqs for Sem 1,2011 implementation.

30/09/2020 Admin: Update to include new assessment and teaching approach fields as per Handbook requirements.

This is a core second year unit in BCS, BSE, BCS/BA, BCS/LLB, and BSc/BCS, and is a core in a computer science major in BSc. It introduces students to the formal theory of languages, models of computation, computability, the limitations of computability and NP-completeness.

It replaces CSE2303 Formal Methods 1 and was introduced in 2007 as part of the level 2 roll out. Theory of Computation is a fundamental topic for computer science and is classed as an essential part of an undergraduate degree in computer science by the ACM.

At the completion of this unit, students should be able to:

020101

This unit introduces formal languages, models of computation, and computational complexity. It looks at what computers can and cannot compute. Topics include finite state automata, regular expressions, grammars, pushdown automata, computable functions, Turing machines, polynomial-time reductions, complexity classes P and NP, and NP-completeness. Skills at writing formal proofs will be developed.

Technological requirements

Students must regularly check Moodle for announcements.

Linux assessment tasks (Assignments 1 & 2) must be done in Linux.

The second assignment will involve the free Turing machine simulator, Tuatara (version 2.1), as well as Linux.

On campus

Lecture and tutorials or workshops or problem classes This teaching and learning approach provides facilitated learning, practical exploration and peer learning.

Laboratory-based classes

These are used to support the practical work students do towards their assignments.

Examination (3 hours and 10 minutes): 50%; In-semester assessment: 50%.

Tutorial preparation 5% Assignment 1 10% Mid-Semester Test 15% Assignment 2 20% Final Exam 50%

1. Tutorial preparation: 5% ULO - all
2. Assignment 1: Regular Expressions and Finite Automata: 10% ULO - 1-3
3. Mid-Semester Test: 15% ULO - 1-5,7-8,10
4. Assignment 2: Lexical Analysis, Parsing, Computability: 20% ULO - 1-8,10
5. Final Examination: 50% ULO - all

Minimum total expected workload equals 12 hours per week comprising:

(a.) Contact hours for on-campus students:

• Three hours of lectures, with (on average) 0.5 hours of these being workshops or other activities focusing on enrichment, consolidation and practice.
• Two hours practical activities, which in some weeks take the form of laboratory classes.

(b.) Additional requirements (all students):

• 7 hours of independent study per week for reading, workshops, prac and assignments.

Tutorial classes should be timetabled into lab rooms with computers and plentiful whiteboard space.

FIT

One of FIT1045, FIT1048, FIT1051, FIT1053, ENG1003, or (FIT1040 and FIT1029) or an equivalent introductory programming unit, and one of MAT1830 or MTH1030, MTH1035 or ENG1005 or equivalent.