[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, 2013

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 requirements

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

Professor Graham Farr

Campus Lecturer

Clayton

Graham Farr

Sunway

Loke Kar Seng

Tutors

Clayton

Rosalito Cruz

Roger Lim

Chris Monteith

Duy Han Phan

Rebecca Robinson

Academic Overview

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

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 learning system.

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.

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

Participation

See participation 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:
    Students are expected to attend and submit/present all of the 5 pracs.
    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

Learning resources

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 Edition, Wiley, New York, ISBN-10: 0471137723.

Monash Library Unit Reading List
http://readinglists.lib.monash.edu/index.html

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

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.monash.edu.au/exams/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

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). Please note that it is your responsibility to retain copies of your assessments.

Online submission

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

Recommended text(s)

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

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

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: www.policy.monash.edu.au/policy-bank/academic/education/index.html

Key educational policies include:

Graduate Attributes Policy

http://www.policy.monash.edu/policy-bank/academic/education/management/monash-graduate-attributes-policy.html

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 http://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/.

Monash University Library

The Monash University Library provides a range of services, resources and programs that enable you to save time and be more effective in your learning and research. Go to 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/.

Disability Liaison Unit

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.

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 the Student Evaluation of Teaching and Units (SETU) survey. 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, see:

www.monash.edu.au/about/monash-directions and on student evaluations, see: www.policy.monash.edu/policy-bank/academic/education/quality/student-evaluation-policy.html

Previous Student Evaluations of this Unit

Student feedback has informed some improvements to the presentation of Prolog and introductory computational complexity.

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

[an error occurred while processing this directive]