Fun Stuff

Logicomix (web-page) by A. Doxiadis and C. Papadimitriou, Bloomsbury Publishing, 2009. A graphic novel subtitled `An Epic Search for Truth’ starring Russel, Whitehead, Frege, Goedel, Turing and many
Every computer scientist should also know xkcd, which releases new comics (on Romance, sarcasm, math, and language) every week.

Study Material

Archive of old Exams, Exercises, and More#

Check out our Sharepoint that contains past exams, exercises, tutorial sheets, videos, and more! Definitely worth a look. Note however that the first 50% of the course have been heavily revised, so the content will only loosely overlap for that part. To access the files, you will have to click on “Documents”. Within the folder displayed you find all our material.

But keep in mind that this is just intended as additional study material. Copying is of course strictly forbidden as this would be academic misconduct.

Short Videos Going through Examples:#

Those videos are a few years old, in particular (way) older than 2024. Therefore, the first six weeks will only have some overlap with the 2024 course or newer, as the focus was still slightly different back then.

Week 1: 01 Boolean Logic
Week 2: 02 Propositional Natural Deduction
Week 3: 03 First Order Natural Deduction
Week 4: 04 Induction
Week 5: 05 Hoare Logic and 06 Intro to Hoare Logic
Week 6: 07 Hoare Logic with Loops + Total Correctness
Week 7: 08 Finite State Automata
Week 8: same as week 7
Week 9: 09 CFLs and Grammars
Week 10: 10 Turing Machines
Week 11: 11 Computability
Week 12: same as above

You may also visit the course’s YouTube channel to check out other useful videos! The credit for all these videos and the YouTube channel goes to David Quarel, one of our previous tutors. (Kudos!)

Reading Material

By Topic / Lecture Week#

Note that the topics provided here are still according to the years up to 2023. Since 2024, the first half has however been significantly revised. That said, there is still a huge overlap so that a lot of the material will still be helpful. However, the new material on Dafny might not be covered in the below.

Topic	Reference
Propositional Logic	[1] Chs 1.1, 1.2, 1.3, and 1.5 [2] Ch 3 [3] Ch 2 [4] Chs 1.1 and 1.2 [5] Chs 2.1, 2.2, 2.3, 2.4, 2.5, and 3.2
Logic as Algebra	[1] Chs 1.4, 1.6, 2.1, and 2.4 [2] Ch 3 [3] Ch 2 [4] Chs 1.1 and 1.2 [5] Chs 2.1, 2.2, 2.3, 2.4, 2.5, and 3.2
First Order Logic	[1] Chs 2.2, 2.3, 2.4, 2.5, 3.1, 3.2, and 3.3 [2] Ch 4 [3] Ch 3 [4] Chs 1.3 and 1.4 [5] Ch 2.6 [7] Chs 12 and 13
All About Induction	[1] Ch 3.1 [2] Ch 5.1 [3] Chs 5.2, 5.3 and 5.6 [4] Ch 3.5 [5] Chs 3.4 and 3.5
Induction for DataTypes	[1] Chs 3.3
Hoare Logic (partial)	[1] Chs 9.4.1, 9.4.2, 9.4.3, and 9.5 [8] Chs Hoare Logic, Part I and Hoare Logic, Part II [9] [10] [11]
Hoare Logic (total)	[1] Chs 9.4.1, 9.4.2, 9.4.3, and 9.5 [8] Chs Hoare Logic, Part I and Hoare Logic, Part II [9] [10] [11]
Models of Computation I	[6] Chs 2.1, 2.2, 2.3, 2.4, 3.1, 3.2, 4.3, and 4.4 [6] Ch 1. intro to Automata [7] Chs 9.1 and 9.2
Models of Computation II	[1] Ch 10 [6] Chs 5.1, 5.2, 5.4, and 6 [7] Chs 10.1, 10.2, 10.3, and 10.8
Turing Machines	[6] Chs 8.2, and 8.6 [7] Ch 6
Halting, NP	[6] Chs 9 and 10

[1]: Winfried Karl Grassmann and Jean-Paul Tremblay. 1996. Logic and Discrete Mathematics: A Computer Science Perspective. Prentice Hall Press, Upper Saddle River, NJ, USA.

[2]: Willem Conradie, Valentin Goranko and Claudette Robinson. 2015. Logic and Discrete Mathematics: a concise Introduction. Chichester, West Sussex, United Kingdom : Wiley. (Available online via the ANU library.)

[3]: Susanna S. Epp. 2010. Discrete Mathematics with Applications. Brooks/Cole Publishing Co., Pacific Grove, CA, USA. (Available online via the ANU library.)

[4]: David J. Hunter. 2010. Essentials of Discrete Mathematics (2nd ed.). Jones and Bartlett Publishers, Inc., USA. (Available online via the ANU library.)

[5]: Harris Kwong. 2015. A Spiral Workbook for Discrete Mathematics. Amazon Digital Services LLC. (Available online here.)

[6]: John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. 2006. Introduction to Automata Theory, Languages, and Computation (3rd Edition). Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA. (Available online via the ANU library.)

[7]: Martin D. Davis, Ron Sigal, and Elaine J. Weyuker. 1994. Computability, Complexity, and Languages (2nd Ed.): Fundamentals of Theoretical Computer Science. Academic Press Prof., Inc., San Diego, CA, USA.

[8]: Benjamin C. Pierce, Arthur Azevedo de Amorim, Chris Casinghino, Marco Gaboardi, Michael Greenberg, Catalin Hritcu, Vilhelm Sjöberg, Andrew Tolmach, and Brent Yorgey. 2018. Programming Language Foundations. Software Foundations series, volume 2. Electronic textbook. (Available here (volume 2).)

[9]: Gordon, “Specification and Verification I”, online.

[10]: C. A. R. Hoare. 1969. An axiomatic basis for computer programming. Commun. ACM 12, 10 (October 1969), 576-580. doi: 10.1145/363235.363259. (Available here.)

[11]: Floyd, R. W. 1967. Assigning Meanings to Programs. Proceedings of Symposium on Applied Mathematics, 19, 19-32. (Available here.)

Material on Haskell#

On Haskell tips, one of our previous tutors (from 2022), Pramo Samarasinghe, has created a short introduction to Haskell. It also contains the Haskell code used in lecture slides and tutorial sheets (update: this probably refers to the code that was previously in the first part and has now been replaced) with the corresponding explanation. Also, as written on our page for the the Lectures page, Haskell is not essential for this course anymore.
Haskell: The Craft of Functional Programming (2e) Simon Thompson, (Addison Wesley). (Many of you will have this book from COMP1100.)
On Haskell tips, our previous tutor (year not recorded) Benjamin Gray has created this. You might find it useful.

Search this site

Resources