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

School of Computer Science and Software Engineering

CITS2211 Discrete Structures

Overview

Welcome to the website for CITS2211 in 2018. This unit introduces students to the mathematical foundations of computer science: basic logic, formal proofs, sets, relations, counting and countability, automata and formal languages.

NEWS
20 July Welcome to the Discrete Structures unit in 2018. All classes for CITS2211 start in the week beginning Monday 30 July, semester 2, week 1. The first class is from 10am to 12 noon, Wednesday, in the Murdoch Lecture Theatre (room G58 in the Arts building).
15 August Note that the first test is this Friday, 17 August, at 11am. See the assessments page for details.

Teaching

Unit coordinator: Arran Stewart
Consultation: Thurs 4-5 pm in CSSE room G.8
Teaching Assistants: Theo Vickery, Manou Rosenberg

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 11am on Fridays. See the Schedule page for details.

Type Time Day Location
Workshop Lecture 10am to 12 Wed Murdoch lecture theatre (Arts G58)
Workshop Lecture 11am to 1pm Friday Clews Lecture Theatre (Physics 2.43)

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.

Assessment

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.