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

: maria.admiraal@waikato.ac.nz

Placement/WIL Coordinator(s)

Tutor(s)

Student Representative(s)

Lab Technician(s)

Librarian(s)

: alistair.lamb@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.

_______________

The learning outcomes for this paper are linked to Washington Accord graduate attributes WA1-WA11. Explanation of the graduate attributes can be found at: https://www.ieagreements.org/

Edit Paper Description Content

Paper Structure

Edit Paper Structure Content

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

Lectures will be in-person, but lecture materials will be available through Moodle and recorded in Panopto. Each week, comprehensive notes will be placed on Moodle, and these will form the basis for the lectures which will generally be on Thursdays and Fridays. (The very first Monday will also be a lecture.)

On Mondays (aside from the very first one) there will be a problem session/tutorial, covering some set problems based on the previous 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, their links with grammars, and be able to build a finite state machine to recognise a given regular language. (WA1)
    Linked to the following assessments:
  • Demonstrate ability to build a Turing machine to perform a task selected from a range of basic computations, and understanding of the notions of computability, effective enumeration and the Halting Problem. (WA1)
    Linked to the following assessments:
  • Demonstrate ability to determine the logical status and equivalence of formulas using a truth table and symbolically, as well as to formulate and test validity of logical inferences. (WA1)
    Linked to the following assessments:
  • Demonstrate understanding of the basic quantifiers of predicate logic, including the concepts of model and validity, as well as of soundneess and completeness in logic, and ability to use the technique of mathematical induction. (WA1)
    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 exam. There is a D-rule applying to the final exam: to obtain a clear pass in the paper, you must obtain at least 50% overall AND at least 40% on the final exam.

If you are enrolled in a BE (Hons) degree: Samples of your work may be required as part of the Engineering New Zealand accreditation process for BE (Hons) degrees. Any samples taken will have the student name and ID redacted. If you do not want samples of your work collected, then please email the engineering administrator, Natalie Shaw (natalie.shaw@waikato.ac.nz ), to opt out.

Edit Additional Assessment Information Content

Assessment Components

Edit Assessments Content

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

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

Component DescriptionDue Date TimePercentage of overall markSubmission MethodCompulsory
1. Assignments and labs
20
2. First in-semester test
14 Sep 2022
6:00 PM
15
3. Second in-semester test
19 Oct 2022
6:00 PM
15
4. Final 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 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 trimester (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)

Edit Linkages Content