[an error occurred while processing this directive] [an error occurred while processing this directive]
[an error occurred while processing this directive]
[an error occurred while processing this directive]
Monash University

FIT2014 Theory of computation - Semester 2, 2012

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 expected 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

Associate Professor David Dowe

Campus Lecturer

Clayton

David Dowe

Graham Farr

Sunway

Loke Kar Seng

Academic Overview

Outcomes

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
  • Graded assignments without comments
  • 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

There has been much positive feedback, including most of the material, the lecturer's understanding and presentation, and at least much of the tutoring.

We will continue to use Moodle to co-ordinate the subject.

Student feedback has suggested that more attention should be paid to the Prolog programming language.  While some students enjoyed it, many found it to be a challenge.  Students are encouraged to take an interest in Prolog before it is first presented in class.

While students liked the material on P, NP and the Cook-Levin theorem, some found it hard or abstract.  The presentation of this material will be modified this time.

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

Recommended text(s)

M. Sipser. (2012). Introduction to the Theory of Computation. (3rd) (ISBN: 9781133187790).

L. Sterling and E. Shapiro. (). Art of Prolog: Advanced Programming Techniques. (2nd) (ISBN: 9780262691635).

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 Tute 1 (no direct assessment)
4 Kleene's Theorem and Lexical Analysis Prac 1: Finite Automata
5 Pumping Lemma and Context Free Grammars Tute 2 (no direct assessment)
6 Pushdown Automata and Parsing Prac 2: Lexical Analysis
7 Chomsky Normal Form and Turing Machines Tute 3 (no direct assessment)
8 Computability and Universal Turing Machines Prac 3: Parsing
9 Decidability and Non-Computability Tute 4 (no direct assessment)
10 Undecidability, and Class P and Class NP Prac 4: Computability
11 Polynomial Reducibility and NP-completeness Tute 5 (no direct assessment)
12 Implications and Revision Prac 5: Cook-Levin and Equivalence
  SWOT VAC No formal assessment is undertaken in 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

Faculty Policy - Unit Assessment Hurdles (http://www.infotech.monash.edu.au/resources/staff/edgov/policies/assessment-examinations/unit-assessment-hurdles.html)

Academic Integrity - Please see the Demystifying Citing and Referencing tutorial at http://lib.monash.edu/tutorials/citing/

Assessment Tasks

Hurdle Requirements

See additional hurdle requirements below.

Participation

See attendance requirements for pracs below.

  • 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.

    Some of the pracs will use the programming language, Prolog, which will be new to many students. Students should familiarise themselves with Prolog as early in semester as possible.
    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.

    Hurdle requirements:
    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.
    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:
    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
    Hurdle requirements:
    The Faculty hurdle requirements apply for the final exam.
    Electronic devices allowed in the exam:
    None

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).

Online submission

If Electronic Submission has been approved for your unit, please submit your work via the VLE site for this unit, which you can access via links in the my.monash portal.

Extensions and penalties

Submission must be made by the due date otherwise penalties will be enforced.

You must negotiate any extensions formally with your campus unit leader via the in-semester special consideration process: http://www.infotech.monash.edu.au/resources/student/equity/special-consideration.html.

Returning assignments

Students can expect assignments to be returned within two weeks of the submission date or after receipt, whichever is later.

Referencing requirements

When referencing, students familiar with LaTeX are encouraged to use LaTeX and BibTeX .

See also the Library Guides for Citing and Referencing at http://guides.lib.monash.edu/content.php?pid=88267&sid=656564

Other Information

Policies

Monash has educational policies, procedures and guidelines, which are designed to ensure that staff and students are aware of the University's academic standards, and to provide advice on how they might uphold them. You can find Monash's Education Policies at:
http://policy.monash.edu.au/policy-bank/academic/education/index.html

Key educational policies include:

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. For Sunway see http://www.monash.edu.my/Student-services, and for South Africa see http://www.monash.ac.za/current/

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. At Sunway, visit the Library and Learning Commons at http://www.lib.monash.edu.my/. At South Africa visit http://www.lib.monash.ac.za/.

Academic support services may be available for students who have a disability or medical condition. Registration with the Disability Liaison Unit is required. Further information is available as follows:

  • Website: http://monash.edu/equity-diversity/disability/index.html;
  • Email: dlu@monash.edu
  • Drop In: Equity and Diversity Centre, Level 1 Gallery Building (Building 55), Monash University, Clayton Campus, or Student Community Services Department, Level 2, Building 2, Monash University, Sunway Campus
  • Telephone: 03 9905 5704, or contact the Student Advisor, Student Commuity Services at 03 55146018 at Sunway

Reading list

Further reading:

Also recommended for Prolog is the WWW resource: www.LearnPrologNow.org

For parts of the course other than Prolog, also useful can be:

Daniel I. A. COHEN (1997), "Introduction to computer theory", 2nd edn., Wiley, New York, ISBN-10: 0471137723.

[an error occurred while processing this directive]