COMP9020
Foundations of Computer Science
Lecture 17: Course Review
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
2
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
Topic 0: Number Theory
2
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
Topic 1: Structures
Sets
Relations
Functions
Graph Theory
2
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
Topic 2: Recursion
Recursion
Induction
Algorithmic
Analysis
2
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
Topic 3: Logic
Boolean Logic
Propositional Logic
2
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
Topic 4: Probability
Combinatorics
Probability
Statistics
2
Course Review
Goal: for you to become a competent computer scientist.
Requires an understanding of fundamental concepts:
Structures
Recursion
Probability
Logic
In CS/CE these are used to:
formalise problem
specifications and
requirements
develop abstract solutions
(algorithms)
analyse and prove
properties of your
programs
2
Outline
Assessment Summary
Examination Philosophy
Content Review
Selection of Sample Questions
3
Assessment Summary
Quizzes: Best 6 out of 10 – (10 marks)
Assignments: 3 assignments worth 13.33 marks each – (40 marks)
Final exam – (50 marks)
NB
You must achieve 40% on the final exam AND 50% overall to pass
the course.
4
Final Exam
Goal: to check whether you are a competent computer scientist.
Requires you to demonstrate:
understanding of mathematical concepts
ability to apply these concepts and explain how they work
Lectures, quizzes and assignments have built you up to this point.
5
Final Exam
Available: Wednesday, 17th August, 13:45 (AEST)
Due: Wednesday, 17th August, 17:00 (AEST)
Access: Inspera through Moodle
15 Questions, 1-3 parts per question (25 parts in total)
Parts are mostly long-answer questions (e.g.
proofs/counterexamples)
Questions equally weighted (parts not necessarily): 12 marks
per question = 180 marks in total
Covers all of the contents of this course up to and including
Week 10.
I will be available (email/forum/zoom) to answer any
questions, but first point of contact should be exams team
6
Materials
The questions are intended to assess your understanding and your
ability rather than your knowledge.
Access to passive sources (i.e. existing material) is permitted –
should be properly referenced.
Accessing active sources (e.g. collaborating with other students,
actively seeking answers through forums/social media, contract
cheating, etc) is a breach of the University’s Plagiarism Policy and
will be subject to disciplinary action as outlined in the Student
code of conduct
Can use the unicode/LATEXeditor on course website;
Strongly recommended to have external writing materials for rough
working
NB
Questions are culturally neutral – no concepts other than those
taught in this course are assumed.
7
Special consideration
Review the UNSW policy on Special Consideration.
UNSW has a “fit-to-sit” policy: by undertaking the assessment you
are declaring that you are fit to do so.
If there are any foreseeable issues you must apply before the exam.
If circumstances prevent you from applying before the exam, you
must apply as soon as possible (within 3 days).
NB
Supplementary exams are only available to students granted
Special Consideration.
8
Technical issues
If you experience technical issues before or during the exam, you
should follow these instructions:
Take screenshots (including time and date) of as many of the
following as possible:
error messages
screen not loading
timestamped speed tests
power outage maps
messages or information from your internet provider regarding
the issues experienced
Make contact with me immediately (through email, ed, or
zoom) and advise me of the issue.
Submit a Special Consideration application immediately at the
conclusion of your assessment and upload your screenshots.
9
Revision Strategy
Re-read lecture slides
Read the corresponding chapters in the book (R & W)
Review/solve assignments and quizzes
Review/solve problem sets
Solve more problems from the books
Attempt sample exam
(Applying mathematical concepts to solve problems is a skill that
improves with practice)
10
Outline
Assessment Summary
Examination Philosophy
Content Review
Selection of Sample Questions
11
Examiner’s comments
The questions are intended to assess your understanding and your
ability rather than your knowledge.
Unless specified, any valid proof technique is acceptable.
Partial marks are always available for incomplete answers.
12
How hard is it?
A common question is how will the exam compare to
assignment/quiz/practice questions?
The exam situation is significantly different to assignments.
You have less time for the exam, so on the face of it questions
may appear harder (even if this is not the case).
I am aware of the reduced timeframe, so exam marking will
likely be more forgiving than assignment marking.
Assignments had a wide range of difficulty.
Answer
Assignment questions (and practice questions) are indicative of the
questions likely to appear on the exam.
13
Assessment
Assessment is about determining how well you understand the
syllabus of this course.
If you can’t demonstrate your understanding, you don’t pass.
In particular, I can’t pass people just because ...
please, please, ... my family/friends will be ashamed of me
please, please, ... I tried really hard in this course
please, please, ... I’ll be excluded if I fail COMP9020
please, please, ... this is my final course to graduate
etc. etc. etc.
(Failure is a fact of life. For example, my scientific papers or project
proposals get rejected sometimes too)
14
Outline
Assessment Summary
Examination Philosophy
Content Review
Selection of Sample Questions
15
Week 1 Recap
What is a proof?
Nature of propositions
Examples of proof strategies
Direct proof, Contrapositive, Proof by contradiction
Number theory
Floor b·c and ceiling d·e functions
Absolute value | · | function
16
Need to know for this course
How to present proofs
17
Week 2 Recap
Sets:
Set notation: ∈, ∅, U , ⊆, {. . .}, [. . .], (. . .)
Set operations: ∩, ∪, c , \, ⊕, Pow(), ×
Defining sets:
Explicitly listing elements
Subsets of a given set
Constructed using set operations
Cardinality: |X | = #(X ) = card(X )
Venn diagrams
18
Need to know for this course
How to define sets
Set operations
Cartesian product
Cardinality computations
19
Week 3 Recap
Formal languages:
Symbols, words, languages
Language definitions: Σ∗, length(), concatenation, Kleene star
Set equality:
Compare elements
A ⊆ B and B ⊆ A
Proofs using the Laws of Set Operations
20
Laws of Set Operations
For all sets A, B, C :
Commutativity A ∪ B = B ∪ A
A ∩ B = B ∩ A
Associativity (A ∪ B) ∪ C = A ∪ (B ∪ C )
(A ∩ B) ∩ C = A ∩ (B ∩ C )
Distribution A ∪ (B ∩ C ) = (A ∪ B) ∩ (A ∪ C )
A ∩ (B ∪ C ) = (A ∩ B) ∪ (A ∩ C )
Identity A ∪ ∅ = A
A ∩ U = A
Complementation A ∪ (Ac) = U
A ∩ (Ac) = ∅
21
Other useful set laws
Idempotence A ∩ A = A
A ∪ A = A
Double complementation (Ac)c = A
Annihilation A ∩ ∅ = ∅
A ∪ U = U
de Morgan’s Laws (A ∩ B)c = Ac ∪ Bc
(A ∪ B)c = Ac ∩ Bc
Theorem (Principle of Duality)
If you can prove A1 = A2 using the Laws of Set Operations then
you can prove dual(A1) = dual(A2)
Theorem (Uniqueness of complement)
A ∩ B = ∅ and A ∪ B = U if, and only if, B = Ac .
22
Need to know for this course
Definitions around formal languages
Proofs using Laws of Set Operations
23
Week 4 Recap
Relations:
Definitions, n-ary relations
Binary Relations:
Representations: Matrix, graphical, directed graph
Relational image (R(A)), converse relation (R←), inverse
image (R←(B)), relation composition (R;S)
Properties: Fun, Tot, Inj, Sur
Properties: Reflexivity, Antireflexivity, Symmetry,
Antisymmetry, Transitivity
Functions: Domain, codomain, image
24
Week 4 Recap
Equivalence Relations:
Generalize equality
Reflexive, Symmetric, Transitive
Equivalence classes, Partitions
Partial Orders:
Generalize ≤
Reflexive, Antisymmetric, Transitive
Hasse diagram, minimum vs minimal, glb/lub, lattice
25
Need to know for this course
Relational image, relational composition
Properties of binary relations – examples and non-examples
Equivalence classes
Hasse diagram, glb/lub
26
Week 5 Recap
Partial Orders:
Reflexive, Antisymmetric, Transitive
Hasse diagram, minimum vs minimal, glb/lub, lattice,
topological sort, product/lexicographic/lenlex order
Functions:
Functional composition: g ◦ f = f ; g
Inverse function: f←, when it is a function
Matrices: Add, Scalar multiplication, Matrix multiplication,
Transpose
big-O notation: O, Ω, Θ
27
Need to know for this course
Hasse diagram, glb/lub, topological sort, lexicographic/lenlex
order
Inverse function, function composition
Basic matrix definitions and operations
How to compare a variety of functions using big-O
28
Week 6 Recap
Graph Theory
Definitions and notation: vertices, edges, paths, cycles,
connectedness, isomorphisms
Important graphs: Trees, Complete graphs, complete k-partite
graphs
Graph traversals: DFS/BFS, Eulerian path/circuit,
Hamiltonian path/cycle
Graph properties: Chromatic number, Clique number,
Planarity
29
Need to know for this course
Graph definitions and important graph classes
How to model “real-world” problems using graphs
How to show/calculate graph properties:
Connectedness
Eulerian/Hamiltonian traversals
Chromatic number
Clique number
Planarity
Interactions between graph properties
30
Week 7 Recap
Recursion: Defining more complex objects/processes in terms of
simpler ones
Recursive datatypes: Natural numbers, Words, Expressions,
Well-formed formulas
Recursive programming/functions: Factorial, concatenate,
length
Recurrence equations
Unrolling
Approximating with big-O
Master Theorem
Induction: Proving properties about recursively defined objects
Basic induction
Variants of basic induction
Structural induction
31
Master Theorem
The following result covers many recurrences that arise in practice
(e.g. divide-and-conquer algorithms)
Theorem
Suppose
T (n) = a · T
(n
b
)
+ f (n)
where f (n) ∈ Θ(nc(log n)k).
Let d = logb(a). Then:
Case 1: If c < d then T (n) = Θ(nd)
Case 2: If c = d then T (n) = Θ(nc(log n)k+1)
Case 3: If c > d then T (n) = Θ(f (n))
32
Need to know for this course
How and when to define datatypes and functions recursively
How to solve recurrence equations (up to big-O)
How to use induction to prove results about natural numbers
How to use structural induction on recursive structures
33
Week 8 Recap
Algorithmic Analysis:
Count “cost” (default: running time) of elementary
operations as a function of (a parameter of) the input
Approximates real-world cost
Using both big-O and worst-case to simplify analysis
Recursive algorithms lead to recurrence equations
Boolean logic
2-element Boolean Algebra
Boolean functions
CNF/DNF, canonical DNF
Karnaugh maps, optimal DNF
34
Need to know for this course
How to compute algorithm run-time in a variety of situations
Properties of 2-element Boolean Algebra
How to compute canonical CNF/DNF
How to prove properties of Boolean Algebras
35
Week 9 Recap
Propositional logic
Syntax:
Well-formed formulas
Parse trees
CNF and DNF
Semantics:
Truth assignments
Truth tables
Tautologies, Contradictions, Contingencies
Logical equivalence
Entailment
36
Need to know for this course
How to prove/disprove logical equivalence and logical
entailment
How to model problems using Propositional Logic
37
Week 10 Recap
Combinatorics
Basic counting rules: Disjoint sets, Cartesian products
Permutations and Combinations
Balls in boxes
Using recursion to count
Approximate counting
Probability
Sample spaces, probability distributions, events
Independence
Recursive probability calculations
Conditional probability
Statistics
Random variables
Expectation, linearity of expectation
Variance, standard deviation
38
Selecting items summary
Selecting k items from a set of n items:
With Order Balls in boxes Formula
replacement matters
Yes Yes Distinguishable balls nk
Multiple balls per box
No Yes Distinguishable balls Π(n, k)
At most one ball per box
No No Indistguishable balls
(n
k
)
At most one ball per box
Yes No Indistinguishable balls
( n
k
)
=
(n+k−1
k
)
Multiple balls per box
39
Need to know for this course
How to count the number of elements in various sets:
Counting selections - which one to apply and how
Identifying symmetries
Using recursion to count
How to calculate probabilities in various situations:
Uniform distributions
Event combinations
Sequences of independent events
Recursive scenarios
Conditional cases
Interaction between properties such as independence,
conditionality
How to calculate expected value of random variables in
various situations
40
Outline
Assessment Summary
Examination Philosophy
Content Review
Selection of Sample Questions
41
Sample Relations Question
Consider the relation R ⊆ R× R defined by aRb if, and only if,
b + 0.5 ≥ a ≥ b − 0.5. Is R
a reflexive?
b antireflexive?
c symmetric?
d antisymmetric?
e transitive?
42
Sample Functions Question
Let Σ = {a, b} and define f : Σ∗ → R recursively as follows:
f (λ) = 0,
f (aw) = 12 +
1
2 f (w) for w ∈ Σ∗, and
f (bw) = −12 + 12 f (w) for w ∈ Σ∗.
Prove that f is injective.
43
Sample Graph Theory Question
Draw a single graph with 6 vertices and 10 edges that satisfies
each of the following:
(a) is planar,
(b) contains a Hamiltonian circuit, and
(c) does not contain an Eulerian path.
44
Sample Logic Question
Let (T ,∧,∨,′ , 0, 1) be a Boolean Algebra. Define ⊕ : T × T → T
as follows:
x ⊕ y = (x ∧ y ′) ∨ (x ′ ∧ y)
a Prove using the laws of Boolean Algebra that for all x ∈ T ,
x ⊕ 1 = x ′.
b Prove using the laws of Boolean Algebra that
x ∧ (y ⊕ z) = (x ∧ y)⊕ (x ∧ z).
c Find a Boolean Algebra (and x , y , z) which demonstrates that
x ⊕ (y ∧ z) 6= (x ⊕ y) ∧ (x ⊕ z)
45
Sample Recursion/Induction Question
Let Σ = {1, 2, 3}.
(a) Give a recursive definition for the function sum : Σ∗ → N
which, when given a word over Σ returns the sum of the
digits. For example sum(1232) = 8, sum(222) = 6, and
sum(1) = 1. You should assume sum(λ) = 0.
(b) For w ∈ Σ∗, let P(w) be the proposition that for all words
v ∈ Σ∗, sum(wv) = sum(w) + sum(v). Prove that P(w)
holds for all w ∈ Σ∗.
(c) Consder the function rev : Σ∗ → Σ∗ defined recursively as
follows:
rev(λ) = λ
For w ∈ Σ∗ and a ∈ Σ, rev(aw) = rev(w)a
Prove that for all words w ∈ Σ∗, sum(rev(w)) = sum(w)
46
Sample Probability Question
A 4-letter word is selected at random from Σ4, where
Σ = {a, b, c , d , e}.
a What is the probability that the letters in the word are
distinct?
b What is the probability that there are no vowels in the word?
c What is the probability that the word begins with a vowel?
d What is the expected number of vowels in the word?
e Let x be the answer to the previous question. What is the
probability of the word having dxe or more vowels?
47