Skip to the content | Change text size
PDF unit guide

FIT2014 Theory of computation - Semester 2, 2011

This unit gives an introduction to formal languages using logic programming and looks at what a computer can compute and what problems are intractable. Examples include why it is so difficult to design timetables, get computers to play Go, or crack a code. Topics include computable functions, finite state automata, regular expressions, grammars, Turing computability, polynomial-time reductions, and NP-completeness.

Mode of Delivery

  • Clayton (Day)
  • Sunway (Day)

Contact Hours

2 hrs lectures/wk, 3 hrs laboratory/fortnight, 2 hrs tutorial/fortnight

Workload

Students will be expecte to spend an average of 12 hours per week:

This will include:

  • 2 hours lecture (each week),
  • either 1 hour tutorial or 3 hour laboratory (alternating weeks),
  • 8 hours of reading, working on exercises and assignment(s), etc.

Unit Relationships

Prohibitions

CSE2303

Prerequisites

FIT1029 and 6 points of level 1 (or above) mathematics

For students in courses 2380, 2770, 0050, 2672, 3517, 3282 and 0085 who commenced prior to 2011: FIT1008/FIT1015 and 6 points of approved mathematics

Chief Examiner

Campus Lecturer

Clayton

David Dowe

Sunway

Loke Kar Seng

Academic Overview

Learning Objectives

At the completion of this unit, students will have -

A knowledge and understanding of:

  • propositional and predicate logic;
  • how to describe languages using Regular Expressions, Finite Automata, Nondeterministic Finite Automata, Context Free Grammars, Pushdown Automata, and Turing Machines;
  • the relationship between Regular Languages, Context Free Languages, Recursive Languages, and Recursive-Enumerable (or Computable) Languages;
  • how to use Turing Machines to represent computable functions;
  • how a Universal Turing machine can simulate any Turing Machine on any input;
  • basic computational complexity theory, including verifiers, polynomial-time reductions and NP-completeness.

Developed attitudes that will allow them to:
  • appreciate the limitations of Regular Languages, Context Free Languages, Recursive Languages, and Computable Languages;
  • comprehend the limitations of computers in terms of the problems they can solve;
  • appreciate that there are many solvable problems which cannot be solved in polynomial time.

Developed the skills to:
  • use propositional logic to represent and analysis problems in the theory of computation;
  • construct Finite Automata, Nondeterministic Automata, and Turing Machines to describe languages;
  • convert Regular Expressions into a Finite Automata;
  • convert Finite Automata into Regular Expressions;
  • find a Regular Grammar for a Regular Language;
  • find a parse tree, leftmost derivation and rightmost derivation for a word in a Context Free Language;
  • know how to show a Context Free Grammar is ambiguous;
  • show a problem is NP-complete.

Graduate Attributes

Monash prepares its graduates to be:
  1. responsible and effective global citizens who:
    1. engage in an internationalised world
    2. exhibit cross-cultural competence
    3. demonstrate ethical values
  2. critical and creative scholars who:
    1. produce innovative solutions to problems
    2. apply research skills to a range of challenges
    3. communicate perceptively and effectively

Assessment Summary

Examination (3 hours): 70%; In-semester assessment: 30%

Assessment Task Value Due Date
Pracs (3 hours) Total of 30% (5 pracs x 6%)
  • Week 4 - Prac 1: Finite Automata.
  • Week 6 - Prac 2: Lexical Analysis.
  • Week 8 - Prac 3: Parsing.
  • Week 10 - Prac 4: Computability.
  • Week 12 - Prac 5: Cook-Levin and Equivalence.
Examination 1 70% To be advised

Teaching Approach

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

Feedback

Our feedback to You

Types of feedback you can expect to receive in this unit are:
  • Informal feedback on progress in labs/tutes
  • Solutions to tutes, labs and assignments

Your feedback to Us

Monash is committed to excellence in education and regularly seeks feedback from students, employers and staff. One of the key formal ways students have to provide feedback is through SETU, Student Evaluation of Teacher and Unit. The University's student evaluation policy requires that every unit is evaluated each year. Students are strongly encouraged to complete the surveys. The feedback is anonymous and provides the Faculty with evidence of aspects that students are satisfied and areas for improvement.

For more information on Monash's educational strategy, and on student evaluations, see:
http://www.monash.edu.au/about/monash-directions/directions.html
http://www.policy.monash.edu/policy-bank/academic/education/quality/student-evaluation-policy.html

Previous Student Evaluations of this unit

If you wish to view how previous students rated this unit, please go to
https://emuapps.monash.edu.au/unitevaluations/index.jsp

Unit Schedule

Week Activities Assessment
0 Register for Tutorials and Laboratory classes in Allocate+ No formal assessment or activities are undertaken in week 0
1 Introduction and Propositional Logic  
2 Predicate Logic and Introduction to Prolog  
3 Regular Expressions and Finite Automata  
4 Kleene's Theorem and Lexical Analysis Prac 1: Finite Automata
5 Pumping Lemma and Context Free Grammars  
6 Pushdown Automata and Parsing Prac 2: Lexical Analysis
7 Chomsky Normal Form and Turing Machines  
8 Computability and Universal Turing Machines Prac 3: Parsing
9 Decidability and Non-Computability  
10 Undecidability, and Class P and Class NP Prac 4: Computability
11 Polynomial Reducibility and NP-completeness  
12 Implications and Revision Prac 5: Cook-Levin and Equivalence
  SWOT VAC No formal assessment is undertaken SWOT VAC
  Examination period LINK to Assessment Policy: http://policy.monash.edu.au/policy-bank/
academic/education/assessment/
assessment-in-coursework-policy.html

*Unit Schedule details will be maintained and communicated to you via your MUSO (Blackboard or Moodle) learning system.

Assessment Requirements

Assessment Policy

To pass a unit which includes an examination as part of the assessment a student must obtain:

  • 40% or more in the unit's examination, and
  • 40% or more in the unit's total non-examination assessment, and
  • an overall unit mark of 50% or more.

If a student does not achieve 40% or more in the unit examination or the unit non-examination total assessment, and the total mark for the unit is greater than 50% then a mark of no greater than 49-N will be recorded for the unit

Assessment Tasks

Participation

  • Assessment task 1
    Title:
    Pracs (3 hours)
    Description:
    On alternating weeks (on five occasions) you will need to complete a prac assignment. Prac assignments are long and are designed to take a significant part of your "home study hours''. This means that you must have a significant proportion of the prac completed before attending the scheduled computer lab. The aim of the computer lab practical is to iron out any bugs, ask any questions about the prac you have not been able to solve on your own, improve the parts that your demonstrator points out as lacking (including comments, algorithms, etc), and get your prac marked. If you do nothing before the scheduled prac, you will soon realise that you do not have enough time to complete it.  The prac sheets will be released approx. every Thursday morning and/or made available in the unit's web page.

    Unless explicitly specified otherwise by both your lecturer and your prac demonstrator, your assignment work is to be done from your Monash student account and demonstrated on one of the Monash computers in your scheduled Monash lab.


    Weighting:
    Total of 30% (5 pracs x 6%)
    Criteria for assessment:

    Every prac sheet contains a guide of the assessment criteria used to assess that prac. In addition, demonstrators might carry with them a marking guide prepared by the lecturer which indicates some details of the marks for each prac question.  You can request the demonstrator to show you the marking guide after he/she has marked your prac.

    Due date:
    • Week 4 - Prac 1: Finite Automata.
    • Week 6 - Prac 2: Lexical Analysis.
    • Week 8 - Prac 3: Parsing.
    • Week 10 - Prac 4: Computability.
    • Week 12 - Prac 5: Cook-Levin and Equivalence.
    Remarks:
    There are two hurdles associated with the pracs. First, you must attend and submit/present at least 4 out of the 5 pracs. Second, you must score at least 50% of the prac mark. A student who does not meet all these hurdles can get a maximum of 49 N for the unit.

    The form(s) of your assignment submission - identical soft electronic and/or hard copies - will be elaborated upon in the assignment statement.  Your assignment will be deemed submitted when all of these versions are submitted.

Examinations

  • Examination 1
    Weighting:
    70%
    Length:
    3 hours
    Type (open/closed book):
    Closed book
    Electronic devices allowed in the exam:
    None
    Remarks:
    There is a hurdle associated with the exam mark:
    • You must score at least 50% of the exam mark.
    • Furthermore, you must score at least 50% overall.

Assignment submission

It is a University requirement (http://www.policy.monash.edu/policy-bank/academic/education/conduct/plagiarism-procedures.html) for students to submit an assignment coversheet for each assessment item. Faculty Assignment coversheets can be found at http://www.infotech.monash.edu.au/resources/student/forms/. Please check with your Lecturer on the submission method for your assignment coversheet (e.g. attach a file to the online assignment submission, hand-in a hard copy, or use an online quiz).

Extensions and penalties

Returning assignments

Other Information

Policies

Student services

The University provides many different kinds of support services for you. Contact your tutor if you need advice and see the range of services available at www.monash.edu.au/students The Monash University Library provides a range of services and resources that enable you to save time and be more effective in your learning and research. Go to http://www.lib.monash.edu.au or the library tab in my.monash portal for more information. Students who have a disability or medical condition are welcome to contact the Disability Liaison Unit to discuss academic support services. Disability Liaison Officers (DLOs) visit all Victorian campuses on a regular basis