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

School of Computer Science and Software Engineering

CITS2211 Discrete Structures

Welcome to the website for CITS2211. This unit introduces students to the mathematical foundations of Computer Science: basic logic, formal proofs, set, relations, automata and formal languages.

20 October The final take home test 06 is now ready for you to enjoy. Published: Thursday 20 October Due date: 10am, Monday 31 October 2016 Visit the Assessment page to download a copy.
20 October Thanks everyone for your feedback on cits2211 this year. I have compiled your responses and also identified some actions to be taken. See feedback response for details.


Unit coordinator: Associate Professor Rachel Cardell-Oliver
Consultation: Mondays 12 to 1pm in CSSE Rm 1.20
Tutor/Lecturer: Dr John McCabe-Dansted (Consultation in tutorial class)
Tutor/Lecturer: Mr Arran Stewart (Consultation in tutorial class)

Students must attend two classes each week. These workshop lecture classes will include lecture segments, tutorial work and assessments (see schedule):

Type Time Day Location
Workshop Lecture 10am to 12 Monday MATH: Weatherburn Lecture Theatre
Workshop Lecture 1pm to 3pmThurssday GGGL: Webb Lecture Theatre

Learning Objectives

On completion of this unit, students will be able to:
  1. Explain, with examples, the basic terminology of sets, counting, relations, propositions, and predicates.
  2. Use rules of inference to construct proofs in propositional and predicate logic.
  3. Describe, select and use common proof techniques including mathematical induction.
  4. Explain, with examples, the basic terminology of finite state machines, Turing machines, and formal languages and grammars.
  5. Design FSMs or grammars to generate or recognise languages.
  6. Explain why the halting problem has no algorithmic solution.
  7. Relate practical examples in Computer Science to an appropriate mathematical model, and interpret the associated operations and terminology in context.


The assessment for CITS2211 comprises weekly assessed tutorials and tests, and a final exam.

Assessment % of final mark Assessment Dates
Tutorial Exercises and Tests 30% about every two weeks
Examination 70% November Examination Period

In order to pass CITS2211 consistent practice and effort are needed throughout the semester. To pass CITS2211 a student is required to achieve ALL of the following:

  1. an overall mark of at least 50%, AND
  2. a mark of at least 30/70 in the exam, AND
  3. satisfactory progress in fortnightly tutorial tests (at least 50%)
If a student does not make satisfactory progress (as defined above) they may be excluded from the examination. Any excluded student will be notified in writing by Week 10 in accordance with Faculty regulations.