COSC3045: pass the exams, not just read the notes
Your complete guide to RMIT University's essentials of computing unit. See where the marks are, work real practice questions, and study with an AI tutor that knows COSC3045.
Sia generates COSC3045 practice questions, walks through fundamental theories of computation and finite state automata step by step, and quizzes you on the material the exam weights most heavily.
Find what is wrong
Can a finite state automaton recognise the language of strings with equal numbers of a's and b's, such as aabb or ab?
Identify what the language requires. To decide equality of counts, the machine must remember how many more a's than b's it has seen so far. That difference is unbounded — it can grow arbitrarily large.
Derive the contradiction. Once two different counts share a state, the machine cannot distinguish them thereafter. Append the same suffix to both and it accepts one string that should be accepted and one that should not. So no such automaton exists.
Place it in the hierarchy. This language is context-free, not regular: a pushdown automaton can recognise it because the stack supplies exactly the unbounded memory the finite automaton lacks. Recognising which model a problem needs is the course's central skill.
The trap: Option B is the intuitive answer and the reason this example is taught: you can build a state per count for any bound you pick, but no finite machine covers all counts, and 'a state for every possible value' is precisely what finite means you cannot have. Option C confuses the regular expressions of computation theory with the extended pattern syntax in programming languages — backreferences take those beyond regular, which is why the theoretical and practical meanings of the term diverge. classic slip!
One exam decides 50% of your grade. Summative. This whole page is built around that.
Overview
What COSC3045 is, and where it sits
COSC3045 is the course where RMIT computing students stop asking how to build software and start asking what can be computed at all. the description states it introduces foundational concepts and techniques in computer science, and that you will learn and apply fundamental theories of computation and how these are realised and related to different programming paradigms.
The published topics are named explicitly and they are the classical core of the subject: various models of computation including finite state automata, grammars, regular expressions, Turing machines and lambda calculus; computational complexity including P versus NP; the limits of computation; and the realisation of computation through programming paradigms such as imperative versus declarative.
Two things distinguish it inside RMIT's computing sequence. It is the only course in our RMIT set that holds a genuine examination — 50% of the grade — where the studio and analytics courses assess entirely through coursework. And it carries two enforced prerequisites, Mathematics for Computing 1 and Algorithms and Analysis, which signal that the mathematical maturity is assumed rather than taught.
Always treat your own course outline and the exam timetable as authoritative.
Difficulty & time commitment
Is COSC3045 hard, and how much time does it take?
COSC3045 is manageable if you keep a weekly rhythm and treat the back half as the main event. The pattern is consistent: it starts gently and steepens, and the heaviest assessment is the part that separates grades.
The difficulty curve and the assessment weighting point the same way: the back half is harder and worth more. Front-loading effort there is the highest-return decision in the unit.
Is this unit for you
Who tends to do well, and who tends to struggle
You will likely do well if
- You are comfortable writing a formal argument, not only writing code.
- Your Algorithms and Analysis material is solid; complexity here builds directly on it.
- You do the take-home assignments fully in writing, since the examination asks for the same style.
- You draw the machines. Automata and pushdown models become obvious once sketched and stay abstract if only read.
You may struggle if
- You expect a programming course; this is a theory course that references programming.
- You memorise results without the arguments, which the 50% examination will not reward.
- You skip the pigeonhole and reduction techniques, which are the two proof patterns the course uses repeatedly.
- You leave lambda calculus and complexity to the end; both arrive late and both are examinable.
- For every model of computation, know exactly what it can and cannot recognise, and one example that separates it from the model below.
- Learn reduction as a technique, not as individual results — it is how almost every hardness argument in the course is built.
- Write proofs out in full sentences. CLO5 asks you to communicate using the technical language of the field correctly, and the examination marks that.
- Connect each abstract model to something you have used: regular expressions to a text search, grammars to a parser, lambda calculus to a functional language.
Syllabus
The 12 topics, topic by topic
The exam-weight marker on each topic shows where the marks concentrate. The amber topics carry the highest exam weight.
T1 · Fundamental theories of computation
Course descriptionWhat a model of computation is, and why several are needed.
T2 · Finite state automata
Course descriptionThe simplest useful computational model, and what it can and cannot recognise.
T3 · Regular expressions and regular languages
Course descriptionThe equivalence between a notation programmers use daily and a formal machine.
T4 · Grammars and language hierarchies
Course descriptionGenerating languages rather than recognising them, and the hierarchy that results.
T5 · Pushdown automata and context-free languages
Standard computation theory canonThe model that steps beyond regular languages, and why parsers need it.
T6 · Turing machines
Course descriptionThe model that defines computability itself.
T7 · Limits of computation and undecidability
Course descriptionProblems no program can solve, and how that is proved rather than asserted.
T8 · Lambda calculus
Course descriptionComputation as function application, and the root of functional programming.
T9 · Computational complexity and P versus NP
Course descriptionClassifying problems by the resources their solutions require.
T10 · Reductions and NP-completeness
Standard computation theory canonShowing a problem is at least as hard as another, the standard proof technique.
T11 · Imperative and declarative paradigms
Course descriptionHow the theory is realised in the two families of programming language.
T12 · Communicating in the technical language of the field
CLO5Stating formal arguments precisely, which the outcomes require and the examination marks.
How it's assessed
Assessment structure
| Component | Weight | Format & timing |
|---|---|---|
| Exam | 50% | Examination, published by RMIT as Assessment Component 3 and supporting all five course learning outcomes. End of semester. Summative. |
| Take-home Assignments | 40% | Take-home assignments, published as Assessment Component 1 and supporting all five course learning outcomes. Across the semester. Continual assessment. |
| Quizzes | 10% | Quizzes, published as Assessment Component 2, supporting course learning outcomes 1, 2 and 3. Across the semester. Continual assessment. |
- The three published components sum to 100. RMIT states plainly that this course has no hurdle requirements, so no component must be passed independently.
- This is the only course in our RMIT set with a genuine examination, and it carries 50% of the grade while supporting all five learning outcomes. The 40% of take-home assignments is the main rehearsal for it, because both ask for the same thing: a formal argument written out, not a program that runs.
This is an exam-cram unit. With the exams at 50% of the grade and the exam alone at 50%, your result is overwhelmingly decided by how well you perform under time pressure. Summative.
Final exam timing: End of semester examination. Confirm the exact date and venue on your exam timetable.
How to actually pass it
A weekly rhythm, two checklists, and the traps to avoid
The unit rewards consistency over cramming, and practice over re-reading. Here is the loop that works, then what to have nailed before each exam.
The weekly loop
Before the mid-semester checklist
- Explain what a model of computation is and why several are needed.
- Construct finite state automata and relate them to regular expressions and regular languages.
- Use grammars to generate languages and place them in the hierarchy.
- Explain pushdown automata and why context-free languages need them.
Before the final heaviest topics
- Describe Turing machines and their role in defining computability.
- Explain undecidability and prove a problem undecidable by reduction.
- Apply lambda calculus and relate it to declarative programming.
- Classify problems by complexity, explain P versus NP and construct reductions.
The mistakes that cost marks
Assuming a finite machine can count. Finite means finitely many states. Any language requiring unbounded counting is beyond a finite automaton, and the pigeonhole argument is how that is proved.
Theoretical and practical regular expressions confused. Backreferences in programming languages take patterns beyond the regular languages the theory describes.
Undecidable read as hard. Undecidable means no algorithm exists at all, for any resources. It is a different claim from computationally expensive.
Results memorised without proofs. The examination supports all five learning outcomes and asks for argument. A remembered result with no reasoning cannot score well.
Teaching team
Who teaches COSC3045
The bios below are factual. We do not rate lecturers; any star ratings are submitted by students who have taken COSC3045.
Teaching team as listed in public course information. AskSia does not rate lecturers; star ratings are submitted by students who have taken COSC3045.
Formula & concept sheet
The vocabulary and formulas you must own
- Model of computation
- A formal system defining what steps a machine may take, and therefore what it can compute.
- Finite state automaton
- A machine with finitely many states and no additional memory; recognises exactly the regular languages.
- Regular language
- A language recognisable by a finite automaton, equivalently describable by a regular expression.
- Grammar
- A set of production rules generating the strings of a language.
- Pushdown automaton
- A finite automaton with a stack; recognises the context-free languages.
- Turing machine
- The model defining computability: a finite control with unbounded tape.
- Undecidable
- Describing a problem for which no algorithm can exist, regardless of available resources.
- Lambda calculus
- A model of computation based on function abstraction and application; the basis of functional programming.
- Computational complexity
- The classification of problems by the resources their solutions require.
- P versus NP
- The open question of whether every problem whose solution is quickly checkable is also quickly solvable.
- Reduction
- Transforming one problem into another to show it is at least as hard; the standard hardness technique.
- Imperative and declarative paradigms
- Programming by specifying steps, versus specifying what is to be computed.
Common acronyms: CLO · DFA · NFA · NP · PDA.
Where it fits
Prerequisites, related units & why it matters
Enforced prerequisites published by RMIT: MATH2411 Mathematics for Computing 1 and COSC2123 Algorithms and Analysis, both of which must be successfully completed before enrolling. Worth 12 credit points, taught face to face at City Campus by the School of Computing Technologies. It contributes to BP094 Bachelor of Computer Science and BP347 Bachelor of Computer Science (Professional).
Your COSC3045 study toolkit
Study the unit with Sia, not just read about it
Each tool already knows COSC3045: your syllabus, your texts, and where the marks are. Grouped by how you study, from first contact to exam week.
FAQ
Frequently asked questions
Is COSC3045 hard?
It rates hard, the highest of our RMIT courses. The material is abstract and proof-oriented, it carries two enforced prerequisites, and it is the only RMIT course in this set with an examination — worth 50%.
What is the assessment breakdown?
Exam 50%, take-home assignments 40%, quizzes 10%. RMIT publishes real component names for this course, unlike several of its business courses.
Are there hurdle requirements?
No. RMIT states plainly that this course has no hurdle requirements, so no single component must be passed on its own.
What do I need before taking it?
Two enforced prerequisites: MATH2411 Mathematics for Computing 1 and COSC2123 Algorithms and Analysis.
Do I write much code?
Less than in other computing courses. the description covers the realisation of computation via programming paradigms, so you will relate theory to imperative and declarative programming, but the assessment is formal reasoning rather than software delivery.
What is the hardest part?
For most students it is the transition from automata, which are concrete and drawable, to undecidability and complexity, where the arguments are proofs about what cannot exist. Practising written proofs rather than reading them is what closes that gap.
Study COSC3045 with Sia
Work through fundamental theories of computation, finite state automata, regular expressions and the rest of the unit with a tutor that knows it and quizzes you on the topics the assessments weight most heavily.
Start studying with Sia
