COSC261-24S1 (C) Semester One 2024

Formal Languages and Compilers

15 points

Details:
Start Date: Monday, 19 February 2024
End Date: Sunday, 23 June 2024
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Sunday, 3 March 2024
  • Without academic penalty (including no fee refund): Sunday, 12 May 2024

Description

This course deals with fundamental concepts and techniques in computer science. It covers automata, formal languages, compilers, computability and complexity theory.

Covid-19 Update: Please refer to the course page on AKO | Learn for all information about your course, including lectures, labs, tutorials and assessments.

We will cover topics from the following list:
• finite automata and regular expressions
• pushdown automata and context-free grammars
• Turing machines and recursively enumerable languages
• undecidability and the halting problem
• complexity classes and the P=NP problem
• lexical analysis and scanners
• syntactic analysis and parsers
• semantic analysis and optimisation
• code generation

Learning Outcomes

1. Differentiate formal languages at the various levels of the Chomsky hierarchy [WA1, WA2]
2. Apply conversions between languages, automata, regular expressions and grammars [WA1, WA3]
3. Use a range of techniques to generate automata and grammars for unfamiliar languages [WA1, WA3]
4. Change a compiler to analyse new program constructs and synthesize code [WA5]
5. Classify undecidable, inefficiently decidable and efficiently decidable problems [WA1, WA2]

University Graduate Attributes

This course will provide students with an opportunity to develop the Graduate Attributes specified below:

Critically competent in a core academic discipline of their award

Students know and can critically evaluate and, where applicable, apply this knowledge to topics/issues within their majoring subject.

Employable, innovative and enterprising

Students will develop key skills and attributes sought by employers that can be used in a range of applications.

Prerequisites

(1) COSC121 or COSC131; (2) COSC122; (3) MATH120

Timetable 2024

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01 Friday 12:00 - 13:00 E8 Lecture Theatre
19 Feb - 24 Mar
22 Apr - 2 Jun
Lecture B
Activity Day Time Location Weeks
01 Tuesday 11:00 - 12:00 E8 Lecture Theatre
19 Feb - 31 Mar
22 Apr - 2 Jun
Lecture C
Activity Day Time Location Weeks
01 Wednesday 12:00 - 13:00 E8 Lecture Theatre
19 Feb - 31 Mar
22 Apr - 2 Jun
Tutorial A
Activity Day Time Location Weeks
01 Wednesday 14:00 - 16:00 Beatrice Tinsley 112 (28/2-27/3, 24/4)
Jack Erskine 136 Lab 4 (1/5-29/5)
26 Feb - 31 Mar
22 Apr - 2 Jun
02 Thursday 14:00 - 16:00 Jack Erskine 111 (29/2-28/3)
Jack Erskine 136 Lab 4 (2/5-30/5)
26 Feb - 31 Mar
29 Apr - 2 Jun
03 Tuesday 12:00 - 14:00 James Logie 104 (27/2-26/3, 23/4)
Jack Erskine 136 Lab 4 (30/4-28/5)
26 Feb - 31 Mar
22 Apr - 2 Jun
04 Friday 14:00 - 16:00 Jack Erskine 111 (1/3-22/3, 26/4)
Jack Erskine 136 Lab 4 (3/5-31/5)
26 Feb - 24 Mar
22 Apr - 2 Jun
05 Monday 15:00 - 17:00 Jack Erskine 101 (26/2-25/3, 22/4)
Jack Erskine 136 Lab 4 (29/4-27/5)
26 Feb - 31 Mar
22 Apr - 2 Jun
06 Friday 10:00 - 12:00 Jack Erskine 443 (1/3-22/3, 26/4)
Jack Erskine 131 Lab 1 (3/5-31/5)
26 Feb - 24 Mar
22 Apr - 2 Jun
07 Thursday 12:00 - 14:00 Jack Erskine 131 Lab 1
26 Feb - 31 Mar
29 Apr - 2 Jun

Examinations, Quizzes and Formal Tests

Test A
Activity Day Time Location Weeks
01 Wednesday 19:00 - 20:30 Jack Erskine 131 Lab 1
25 Mar - 31 Mar
02 Wednesday 19:00 - 20:30 Jack Erskine 133 Lab 2
25 Mar - 31 Mar
04 Wednesday 19:00 - 20:30 Jack Erskine 136 Lab 4
25 Mar - 31 Mar
05 Wednesday 19:00 - 20:30 Jack Erskine 001 Computer Lab
25 Mar - 31 Mar
07 Wednesday 19:00 - 20:30 Jack Erskine 248 Computer Lab
25 Mar - 31 Mar
Test B
Activity Day Time Location Weeks
01 Wednesday 19:00 - 20:30 Jack Erskine 131 Lab 1
29 Apr - 5 May
02 Wednesday 19:00 - 20:30 Jack Erskine 133 Lab 2
29 Apr - 5 May
03 Wednesday 19:00 - 20:30 Jack Erskine 134 Lab 3
29 Apr - 5 May
04 Wednesday 19:00 - 20:30 Jack Erskine 136 Lab 4
29 Apr - 5 May
05 Wednesday 19:00 - 20:30 Jack Erskine 001 Computer Lab
29 Apr - 5 May
06 Wednesday 19:00 - 20:30 Jack Erskine 010 Computer Lab
29 Apr - 5 May
07 Wednesday 19:00 - 20:30 Jack Erskine 248 Computer Lab
29 Apr - 5 May

Timetable Note

Depending on final student numbers, some of the advertised lab/tutorial streams may not run. Final lab/tutorial options will be available for self-allocation closer to the start of the semester through My Timetable.

Course Coordinator / Lecturer

Walter Guttmann

Tutor

Katia De Lu

Assessment

Assessment Due Date Percentage 
Quizzes 10%
Assignment Superquiz 10%
Test 1 15%
Test 2 20%
Final Exam 45%


In the case of an emergency that affects the whole course, the course coordinator may change the nature, weighting and timing of assessments, e.g., tests and exam may be replaced with assignments of the same weight or different weight at a different time or date (which, under certain circumstances, may be outside the prescribed course dates).

Textbooks / Resources

No textbooks are required, but see the following book for additional information:
• Carol Critchlow and David Eck; Foundations of Computation; version 2.3.2, 2011, available here

More advanced or comprehensive books are:
• Michael Sipser; Introduction to the Theory of Computation; third edition, Cengage Learning, 2013
• John Hopcroft, Rajeev Motwani and Jeffrey Ullman; Introduction to Automata Theory, Languages and Computation; Pearson, 2006
• Dexter Kozen; Automata and Computability; Springer, 1997
• Reinhard Wilhelm and Dieter Maurer; Compiler Design; Addison-Wesley, 1995
• Niklaus Wirth; Compiler Construction; Addison-Wesley, 1996
• Alfred Aho, Monica Lam, Ravi Sethi and Jeffrey Ullman; Compilers: Principles, Techniques, and Tools; second edition, Pearson, 2007

Notes

There are several important documents available online about departmental regulations, policies and guidelines at the following site. We expect all students to be familiar with these.

Notices about this class will be posted to the class forum in the Learn system.

COSC students will also be made members of a class called “CSSE Notices”, where general notices will be posted that apply to all classes (such as information about building access or job opportunities).

Additional Course Outline Information

Grade moderation

The Computer Science department's grading policy states that in order to pass a course you must meet two requirements:
1. You must achieve an average mark of at least 50% over all assessment items.
2. You must achieve an average mark of at least 45% over tests and exam.

If you satisfy both these criteria, your grade will be determined by the following University-wide scale for converting marks to grades: an average mark of 50% is sufficient for a C- grade, an average mark of 55% earns a C grade, 60% earns a C+ grade and so forth. However if you do not satisfy both the passing criteria you will be given either a D or E grade depending on marks. Marks are sometimes scaled to achieve consistency between courses from year to year.

Students may apply for special consideration if their performance in an assessment is affected by extenuating circumstances beyond their control.

Applications for special consideration should be submitted via the Examinations Office website within five days of the assessment.

Where an extension may be granted for an assessment, this will be decided by direct application to the Department and an application to the Examinations Office may not be required.

Special consideration is not available for items worth less than 10% of the course.

Students prevented by extenuating circumstances from completing the course after the final date for withdrawing, may apply for special consideration for late discontinuation of the course. Applications must be submitted to the Examinations Office within five days of the end of the main examination period for the semester.

Special Consideration Applications for the Final Exam

Please click HERE for the CSSE Department's policy for the academic remedy of applications for a special consideration for final exams.

Indicative Fees

Domestic fee $942.00

International fee $4,988.00

* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.

For further information see Computer Science and Software Engineering .

All COSC261 Occurrences

  • COSC261-24S1 (C) Semester One 2024