COMPX361-20B (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)

Tim Stokes

Tim Stokes
4131
G.3.11
See Moodle
tim.stokes@waikato.ac.nz

Administrator(s)

: maria.admiraal@waikato.ac.nz
: rachael.foote@waikato.ac.nz

Placement/WIL 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).

Lecture materials will be available through Moodle and recorded in Panopto. Each week, comprehensive notes will be placed on Moodle, and these will be supplemented with videos to help motivate the ideas and guide your study. This material should be worked on during the first three days of each week.

On Thursdays there will be a LIVE problem session/tutorial, covering some set problems based on that week's material. To get the most out of this time, please think about the problems first. This material is excellent preparation for upcoming assignments and tests.

You are also encouraged to either meet the lecturer in his office to obtain assistance (email tim.stokes@waikato.ac.nz, or just try dropping by), or else email queries to him. There will also be a class forum available for student discussions, which the lecturer will contribute to from time to time.

Edit Paper Structure Content

Learning Outcomes

Edit Learning Outcomes Content

Students who successfully complete the paper 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:
  • Demonstrate understanding of the concepts of soundneess and completeness in logic.
    Linked to the following assessments:
Edit Learning Outcomes Content
Edit Learning Outcomes Content

Assessment

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

Assessment Components

Edit Assessments Content

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

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

Component DescriptionDue Date TimePercentage of overall markSubmission MethodCompulsory
1. Assignments and labs
20
2. First in-semester test
9 Sep 2020
6:00 PM
20
  • Online: Submit through Moodle
3. Second in-semester test
14 Oct 2020
6:00 PM
20
  • Online: Submit through Moodle
4. Final Test
40
  • Online: Submit through Moodle
✔
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 weekly materials provided on Moodle.
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
Materials are available in 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 or MATHS202 or COMPX201 or COMPX241

Corequisite(s)

Equivalent(s)

Restriction(s)

Restricted papers: COMP235 and COMP340

Edit Linkages Content