COSC432-22S2 (C) Semester Two 2022

Relational Methods

15 points

Details:
Start Date: Monday, 18 July 2022
End Date: Sunday, 13 November 2022
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Sunday, 31 July 2022
  • Without academic penalty (including no fee refund): Sunday, 2 October 2022

Description

This course covers the algebraic structure of binary relations and their use for formally specifying and reasoning about programs, graphs and models described in predicate logic. It presents the mathematics of relational programming, modelling, algorithm development and correctness proofs, and tools supporting these activities.

2022 Covid-19 Update: Please refer to the course page on AKO | Learn for all information about your course, including lectures, labs, tutorials and assessments.

Topics
In this course we explore binary relations and their application in modelling. We will cover a selection of topics from the following, non-exclusive list:
• foundations
 - relations
 - orders
 - lattices

• applications
 - graphs: transitive closure, reachability, matchings, cycles, confluence
 - modelling: two-person games, social choice, preference
 - algorithm development: relational specification, program transformation
 - program semantics: verification, preconditions, fixpoints, computation models

• tools
 - relational programming and modelling languages: Alloy, RelView
 - counterexample generators: Mace4, Nitpick
 - automated theorem provers: Isabelle, Prover9

Learning Outcomes

  • After completing the course you will
  • know relations, basic relational operations and their properties,
  • understand the matrix and graph representations of relations,
  • be able to perform specific modelling tasks using relations,
  • be able to formally reason about relations,
  • be able to use tools for programming, modelling or reasoning with relations,
  • be aware of program semantics,
  • be aware of the abstraction provided by relations.

Prerequisites

(1) at least one of COSC261, COSC262; and (2) at least one of MATH120, MATH230

Timetable 2022

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01 Wednesday 13:00 - 15:00 Jack Erskine 111
18 Jul - 28 Aug
12 Sep - 23 Oct
Tutorial A
Activity Day Time Location Weeks
01 Thursday 13:00 - 15:00 Jack Erskine 445
18 Jul - 28 Aug
12 Sep - 23 Oct

Timetable Note

Please note that the course activity times advertised here are currently in draft form, to be finalised on Monday 31 January 2022 for S1 and whole year courses, and Monday 27 June 2022 for S2 courses. Please do hold off enquiries about these times till those finalisation dates.

Course Coordinator

Walter Guttmann

Assessment

Assessment Due Date Percentage 
Assignment 1 25%
Assignment 2 25%
Tutorial Participation 5%
Final Exam 45%


2022 Covid-19 Update: Please refer to the course page on AKO | Learn for all information about your course, including lectures, labs, tutorials and assessments.

Textbooks / Resources

Recommended Reading

Bird, Richard , Moor, Oege de; Algebra of programming ; Prentice Hall, 1997.

C. Brink, W. Kahl, G. Schmidt; Relational methods in computer science ; Springer, 1997.

Jackson, Daniel; Software abstractions : logic, language, and analysis ; Rev. ed; MIT Press, 2012.

Schmidt, Gunther; Relational mathematics ; Cambridge University Press, 2011.

Schmidt, Gunther , Strohlein, Thomas; Relations and graphs : discrete mathematics for computer scientists ; New York : Springer-Verlag, 1993.

Course links

Course Information on Learn

Additional Course Outline Information

Grade moderation

The Computer Science department's grading policy states that in order to pass a course you must meet two requirements:
1. You must achieve an average mark of at least 50% over all assessment items.
2. You must achieve an average mark of at least 45% in the exam.

If you satisfy both these criteria, your grade will be determined by the following University-wide scale for converting marks to grades: an average mark of 50% is sufficient for a C- grade, an average mark of 55% earns a C grade, 60% earns a C+ grade and so forth. However if you do not satisfy both the passing criteria you will be given either a D or E grade depending on marks. Marks are sometimes scaled to achieve consistency between courses from year to year.

Students may apply for special consideration if their performance in an assessment is affected by extenuating circumstances beyond their control.

Applications for special consideration should be submitted via the Examinations Office website within five days of the assessment.

Where an extension may be granted for an assessment, this will be decided by direct application to the Department and an application to the Examinations Office may not be required.

Special consideration is not available for items worth less than 10% of the course.

Students prevented by extenuating circumstances from completing the course after the final date for withdrawing, may apply for special consideration for late discontinuation of the course. Applications must be submitted to the Examinations Office within five days of the end of the main examination period for the semester.

Indicative Fees

Domestic fee $1,051.00

* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.

For further information see Computer Science and Software Engineering .

All COSC432 Occurrences

  • COSC432-22S2 (C) Semester Two 2022