The University of Western Australia
School of Computer Science and Software Engineering

School of Computer Science and Software Engineering

CITS2211 Discrete Structures


Lecture handouts and weekly workshop exercises can be downloaded from the Resources page. The order or delivery date of lectures on this page may change during the semester.

Recordings of the lecture-style portions of the lecturer workshops will be available through LMS although personal attendance at lectures and tutorials is recommended. Please note that recordings sometimes fail. Also, the workshop-style segments of the sessions cannot always be recorded, due to their highly interactive nature. All material for this unit (except the lecture recordings) will be available only from this web site.

Readings for this course are taken from

See the Assessment page for details of the in-class and take-home tests. Note that this year tests will be held at 11am on Fridays.

Week Test
(Fri 11am)
Workshop Lecture
(Wed 10am–12)
Workshop Lecture
(Fri 11am–1pm)
Jul 29
Introduction Propositions MCS ch 1 What is a proof
Aug 5
Predicates Axioms, Validity, Satisfiability MCS ch 3 Logical Formulas
Aug 12
Yes (in class) Proofs (intro) Test MCS ch1 What is a proof
Aug 19
Proof by Induction Induction (cont.) MCS ch 5 Induction
Aug 26
Sets Binary Relations MCS ch 4 Mathematical Data Types
Sep 2
Yes (in class) Functions Test MCS ch 4 (on functions)
Sep 9
Partial orders Equivalence Relations MCS 10.6 POs, 10.10 ERs, MCS ch 15 Cardinality Rules
Sep 16
Yes (take home) Cardinality Countability MCS ch 8 (8.1 Infinite Sets)
Sep 23
Finite State Machines Non-deterministic FSMs ITC ch 1

Sep 30
Mid-semester study week
Oct 7
Yes (take-home) Regular Languages Regular Languages ITC ch 1
Oct 14
Pumping Lemma for Regular Languages Context Free Languages and Pushdown Machines ITC ch 2
Oct 21
Turing Machines Halting Problem ITC ch 3 and 4