COMPX361-19B (HAM)

Logic and Computation

15 Points

Edit Header Content
Division of Health Engineering Computing & Science
School of Computing and Mathematical Sciences
Department of Computer Science

Staff

Edit Staff Content

Convenor(s)

Lecturer(s)

Administrator(s)

: rachael.foote@waikato.ac.nz

Placement Coordinator(s)

Tutor(s)

Student Representative(s)

Lab Technician(s)

Librarian(s)

: debby.dada@waikato.ac.nz

You can contact staff by:

  • Calling +64 7 838 4466 select option 1, then enter the extension.
  • Extensions starting with 4, 5, 9 or 3 can also be direct dialled:
    • For extensions starting with 4: dial +64 7 838 extension.
    • For extensions starting with 5: dial +64 7 858 extension.
    • For extensions starting with 9: dial +64 7 837 extension.
    • For extensions starting with 3: dial +64 7 2620 + the last 3 digits of the extension e.g. 3123 = +64 7 262 0123.
Edit Staff Content

Paper Description

Edit Paper Description Content

This paper is about the theoretical and mathematical ideas that underlie modern computing and computational thinking.

In the first section, formal languages, machines, and models of computation are introduced and studied in some detail. Topics include: finite-state automata and regular languages; Turing machines; the Church-Turing Thesis; the Halting Problem; formal grammars.

In the second section, we take a formal approach to propositional and especially predicate logic, including an introduction to the powerful technique of mathematical induction.

Edit Paper Description Content

Paper Structure

Edit Paper Structure Content

The paper will be taught by Dr Tim Stokes (Mathematics).

There are three teaching hours per week, as well as some lab verification time. One of the teaching hours (usually the Thurssday) will be used as a problem session/tutorial.

All classes will be recorded using Panopto.

Edit Paper Structure Content

Learning Outcomes

Edit Learning Outcomes Content

Students who successfully complete the course should be able to:

  • Demonstrate understanding of the concept of a formal language and the ways of combining languages, especially the special case of regular languages.
    Linked to the following assessments:
  • Build a finite state machine to recognise a given regular language, and determine the regular language accepted by a given finite state machine.
    Linked to the following assessments:
  • Build a Turing machine to perform a task selected from a range of basic computations.
    Linked to the following assessments:
  • Demonstrate understanding of the notions of computability, effective enumeration and the Halting Problem.
    Linked to the following assessments:
  • Demonstrate understanding of the notion of a formal grammar and the main types, as well as their links to automata.
    Linked to the following assessments:
  • Analyse the logical status of a formula using a truth table.
    Linked to the following assessments:
  • Determine the equivalence of formulas, either axiomatically or using disjunctive normal form.
    Linked to the following assessments:
  • Demonstrate understanding of the basic quantifiers of predicate logic, including the concepts of model and validity.
    Linked to the following assessments:
  • Demonstrate understanding of and be able to use the method of mathematical induction in a variety of settings.
    Linked to the following assessments:
Edit Learning Outcomes Content
Edit Learning Outcomes Content

Assessment

Edit Assessments Content
This paper is assessed by two written tests, as well as by roughly weekly items including four written assignments and four computer-based lab exercises, and by the final exam.
Edit Additional Assessment Information Content

Assessment Components

Edit Assessments Content

The internal assessment/exam ratio (as stated in the University Calendar) is 50:50. There is no final exam. The final exam makes up 50% of the overall mark.

The internal assessment/exam ratio (as stated in the University Calendar) is 50:50 or 0:0, whichever is more favourable for the student. The final exam makes up either 50% or 0% of the overall mark.

Component DescriptionDue Date TimePercentage of overall markSubmission MethodCompulsory
1. Assignments and labs
20
2. First in-semester test
4 Sep 2019
6:00 PM
15
3. Second in-semester test
9 Oct 2019
6:00 PM
15
4. Exam
50
Assessment Total:     100    
Failing to complete a compulsory assessment component of a paper will result in an IC grade
Edit Assessments Content

Required and Recommended Readings

Edit Required Readings Content

Required Readings

Edit Required Readings Content
There is no required reading beyond the materials provided on Moodle, which is based on the lecture slides.
Edit Required Readings Content

Recommended Readings

Edit Recommended Readings Content
Some supplementary material will be made available on Moodle, and some students may find this helpful.


Edit Recommended Readings Content

Other Resources

Edit Other Resources Content
All classes are recorded using Panopto.
Edit Other Resources Content

Online Support

Edit Online Support Content

Moodle is used throughout.

Edit Online Support Content

Workload

Edit Workload Content
The overall workload should be one-quarter of a full-time workload. You should expect to spend time each week reading, thinking, preparing for tests, and doing assignments and/or labs, in addition to attending classes. Note that the mid-semester break weeks are considered working time for students, as is the study week prior to the examinations: a student at Waikato should be working 15 weeks per semester (plus exams).
Edit Workload Content

Linkages to Other Papers

Edit Linkages Content

Prerequisite(s)

Prerequisite papers: MATHS135

Corequisite(s)

Equivalent(s)

Restriction(s)

Restricted papers: COMP235 and COMP340

Edit Linkages Content