COMP1600/COMP6260: Foundations of Computing

Runs	Semester 2
Lecturers	Dirk Pattinson, Victor Rivera
Webpage	https://cs.anu.edu.au/courses/comp1600/

COMP1600 is a first year second semester course which serves as an introduction to theoretical computer science. It's unlikely you will have seen many of the concepts taught before even if you have lots of programming experience. It has a similar structure to COMP1100: weekly lectures and labs, 3 assignments, a mid-semester exam and a final exam. It also has weekly quizzes worth 1% each with unlimited retries - make sure to set a calendar reminder to do them because they're very easy to forget!

There is no programming in this course. Instead, there's lots of maths proofs. You do a few maths proofs about Haskell programs (hence the COMP1100 prerequisite) but you never write code yourself during the course.

For the first 3 weeks you will learn about formal Boolean logic and how to prove logical statements with natural deduction. Then you'll move on to program proofs with structural induction and Hoare logic for 3 weeks. Then you'll learn about automata, Turing machines, grammars, regular expressions, and formal languages for 4 weeks. Finally, you'll learn about decidability/computability and computational complexity.

Many people without much of a background in maths find the course quite difficult. If you don't have much background, make sure to learn all the notation early on and try doing the quizzes and/or assignments in a study group.

In 2021, the final exam was quite difficult. It's worth trying really hard on the assignments and doing all the quizzes to make sure you get a mark you're happy with. Assignment and exam marking is very black and white: if a question says to write a proof in full detail, you will lose marks if a single step is missing in a 2 page long proof, so err on the side of verbosity. Some quizzes have trick questions too.