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 2019. 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 2019. All classes for CITS2211 start in the week beginning Monday 29 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).
09 Aug The first test is next Friday, 16 August, at 11am. See the assessments page for details.
04 Sep The second test is on Friday, 6 September, at 11am. See the assessments page for details.
04 Sep The third test was made available on Friday, 20 September, and was due on Friday, 27 September, at 11am. See the assessments page for further details.
11 Oct The fourth test was made available on Friday, 11 October, and was due on Friday, 18 October, at 11am. See the assessments page for further details.

Announcements

Announcements will be made in the lecture-workshops, and repeated in the Help2211 discussion forum – not via the LMS. It is your responsibility to keep up to date with these, to ensure you do not miss any important information.

Teaching

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

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; occasionally if more material needs to be covered, we’ll instead have two 50 minutes sessions with a 10-min break. 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 Woolnough LT

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. Time spent in class (and reviewing class materials) should account for about one-third of the effort required for this unit. The remainder of your time should be spent attempting exercises and gaining practice in problem-solving and writing proofs.