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 in 2017. This unit introduces students to the mathematical foundations of Computer Science: basic logic, formal proofs, sets, relations, counting and countability, automata and formal languages.

20 July Welcome to the Discrete Structures unit in 2017. All classes for CITS2211 start in the week beginning Monday 31 July, semester 2, week 1. The first class is from 10am to 12 noon in the Gentilli Lecture theatre (GGGL 131)


Unit coordinator: Associate Professor Rachel Cardell-Oliver
Consultation: Mondays 12 to 1pm in CSSE Rm 1.20
Teaching Assistant: Dr John McCabe-Dansted
Teaching Assistant: Mr Arran Stewart

Students must attend two classes each week. These workshop-lecture classes will include lecture segments, tutorial work and assessments. The classes will usually run for 90 minutes. In-class tests will be held at 1pm on Thursdays. See the Schedule page for details.

Type Time Day Location
Workshop Lecture 10am to 12 Monday GGGL: Gentilli Lecture Theatre
Workshop Lecture 1pm to 3pmThursday GGGL: Gentilli 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 fortnightly tests, and a final exam.

Assessment % of final mark Assessment Dates
Fortnightly Tests 40% about every two weeks
Examination 60% 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 40% in the exam, AND
  3. satisfactory progress in fortnightly tutorial tests (at least 40%)
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.