Untitled
COEN240 FINAL REVIEW PODCAST SCRIPT WITH QUESTIONS AND EXPLANATIONS
Welcome to the COEN240 final review. In this podcast, we are going to go through the most important exam-style questions and explain how to solve each one. The goal is not just to memorize answers. The goal is to recognize the type of question and know what steps to do.
QUESTION 1: Predicate Logic
Translate this sentence into predicate logic:
“Everyone in your class has a cellular phone.”
Let S(x) mean “x is a student in your class.”
Let C(x) mean “x has a cellular phone.”
Explanation:
The keyword “everyone” means we use the universal quantifier, ∀. Since the domain may be all people, we need to say: if x is a student in your class, then x has a cellular phone.
So the answer is:
∀x(S(x) → C(x))
Memory rule: Every, all, and each usually use ∀ with an implication arrow.
Now translate:
“Some student in your class has a cellular phone.”
The keyword “some” means we use the existential quantifier, ∃. Since the student must both be in the class and have a phone, we use AND.
The answer is:
∃x(S(x) ∧ C(x))
Memory rule: Some, somebody, and exists usually use ∃ with AND.
Now translate:
“Some student in your class does not have a cellular phone.”
We still use ∃ because of “some.” The phrase “does not have” means we negate C(x).
The answer is:
∃x(S(x) ∧ ¬C(x))
So for predicate logic, remember:
All means ∀ and usually uses arrow.
Some means ∃ and usually uses AND.
Not means use ¬.
QUESTION 2: Rules of Inference
Name the rule of inference used:
“Alice is a math major. Therefore, Alice is either a math major or a computer science major.”
Explanation:
The pattern is:
p
Therefore p ∨ q
This rule is called Addition.
You are allowed to add an OR statement because if p is true, then p OR q is automatically true.
Next question:
“If it rains, then the race is canceled. It rains. Therefore, the race is canceled.”
Explanation:
The pattern is:
p → q
p
Therefore q
This rule is Modus Ponens.
Memory rule: Modus Ponens confirms the first part, so you get the result.
Next question:
“If I study, then I pass. If I pass, then I graduate. Therefore, if I study, then I graduate.”
Explanation:
The pattern is:
p → q
q → r
Therefore p → r
This is Hypothetical Syllogism.
Memory rule: Hypothetical Syllogism chains arrows together.
Next question:
“It is either sunny or cloudy. It is not sunny. Therefore, it is cloudy.”
Explanation:
The pattern is:
p ∨ q
¬p
Therefore q
This is Disjunctive Syllogism.
Memory rule: Disjunctive Syllogism eliminates one side of an OR statement.
QUESTION 3: Rules of Inference Proof
Use rules of inference to prove the conclusion.
Premises:
¬p ∧ q
r → p
¬r → s
s → t
Conclusion:
t
Explanation:
We want to reach t. The last premise says s → t, so we need to prove s first.
Step 1:
¬p ∧ q
Reason: Premise
Step 2:
¬p
Reason: Simplification from step 1
Step 3:
r → p
Reason: Premise
Step 4:
¬r
Reason: Modus Tollens from step 2 and step 3
Why? Because r → p means if r happens, p happens. But we know p is false, so r must be false.
Step 5:
¬r → s
Reason: Premise
Step 6:
s
Reason: Modus Ponens from step 4 and step 5
Step 7:
s → t
Reason: Premise
Step 8:
t
Reason: Modus Ponens from step 6 and step 7
Conclusion: t is proven.
QUESTION 4: Set Operations
Let:
A = {1, 3, 5, 7, 9}
B = {0, 1, 2, 3, 4, 5}
C = {5, 6, 7, 8, 9}
Find A ∩ B ∩ C.
Explanation:
Intersection means common elements only. We need elements that appear in all three sets.
A and B have 1, 3, and 5 in common.
Now compare with C. Only 5 is also in C.
Answer:
{5}
Find A ∪ B ∪ C.
Explanation:
Union means combine everything with no repeats.
A, B, and C together contain:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Answer:
{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
Find (A ∪ B) ∩ C.
Explanation:
Do the parentheses first.
A ∪ B = {0, 1, 2, 3, 4, 5, 7, 9}
Now intersect with C = {5, 6, 7, 8, 9}.
Common elements are 5, 7, and 9.
Answer:
{5, 7, 9}
Find (A ∩ B) ∪ C.
Explanation:
Do the parentheses first.
A ∩ B = {1, 3, 5}
Now union with C = {5, 6, 7, 8, 9}.
Answer:
{1, 3, 5, 6, 7, 8, 9}
Memory rule:
Union means combine.
Intersection means common.
Always do parentheses first.
QUESTION 5: Summations
Find the sum from i = 1 to 25 of i.
Explanation:
This means:
1 + 2 + 3 + ... + 25
Use the formula:
n(n + 1)/2
Substitute n = 25:
25(26)/2 = 650/2 = 325
Answer:
325
Find the sum from i = 1 to 10 of i squared.
Explanation:
Use the formula:
n(n + 1)(2n + 1)/6
Substitute n = 10:
10(11)(21)/6
10 times 11 is 110.
110 times 21 is 2310.
2310 divided by 6 is 385.
Answer:
385
Find the sum from i = 0 to 8 of 2^i.
Explanation:
This is:
2^0 + 2^1 + 2^2 + ... + 2^8
So it is:
1 + 2 + 4 + 8 + ... + 256
For powers of 2 from 0 to n, the shortcut is:
2^(n+1) - 1
Here n = 8:
2^9 - 1 = 512 - 1 = 511
Answer:
511
Find the sum from i = 1 to 6 of 3i + 2.
Explanation:
Split it into two sums:
Σ(3i + 2) = 3Σi + Σ2
From 1 to 6:
Σi = 1 + 2 + 3 + 4 + 5 + 6 = 21
Σ2 means add 2 six times:
2 + 2 + 2 + 2 + 2 + 2 = 12
So:
3(21) + 12 = 63 + 12 = 75
Answer:
75
QUESTION 6: Counting
How many strings of length 8 can be made using 26 lowercase English letters if repetition is allowed?
Explanation:
There are 8 positions.
Each position has 26 choices.
Because repetition is allowed, each position stays 26.
So:
26^8
Answer:
208,827,064,576
Now what if repetition is not allowed?
Explanation:
The first position has 26 choices.
The second has 25.
The third has 24.
Keep going for 8 positions.
So:
26 × 25 × 24 × 23 × 22 × 21 × 20 × 19
Answer:
62,990,928,000
Now what if the string must start with a vowel?
Explanation:
The first position must be a vowel.
There are 5 vowels: a, e, i, o, u.
The remaining 7 positions can be any lowercase letter, so each has 26 choices.
So:
5 × 26^7
Answer:
40,159,050,880
Memory rule:
If repetition is allowed, use power.
If repetition is not allowed, choices decrease.
If there is a restriction, handle the restricted position first.
QUESTION 7: Permutations and Combinations
How many ways can 3 winners be chosen from 25 students for first, second, and third place?
Explanation:
First, second, and third are different positions, so order matters.
Use permutation:
25P3 = 25 × 24 × 23
Answer:
13,800
Now how many ways can 3 students be chosen from 25 if order does not matter?
Explanation:
This is just choosing a group. Order does not matter.
Use combination:
25C3 = (25 × 24 × 23)/(3 × 2 × 1)
25 × 24 × 23 = 13,800
3 × 2 × 1 = 6
13,800 ÷ 6 = 2,300
Answer:
2,300
Now how many arrangements of A, B, C, D, E, F contain the block AB?
Explanation:
Treat AB as one object.
So instead of 6 separate letters, we have:
AB, C, D, E, F
That is 5 objects.
Number of arrangements:
5! = 5 × 4 × 3 × 2 × 1 = 120
Answer:
120
Memory rule:
Order matters means permutation.
Order does not matter means combination.
A required block becomes one object.
QUESTION 8: Composition of Relations
Let A = {1, 2, 3}
R = {(1,2), (2,3), (3,1)}
S = {(2,1), (3,2), (1,3)}
Find S composed with R.
Explanation:
S composed with R means do R first, then S.
R sends:
1 to 2
2 to 3
3 to 1
S sends:
2 to 1
3 to 2
1 to 3
Now follow the chain:
Start with 1:
R sends 1 to 2.
S sends 2 to 1.
So we get (1,1).
Start with 2:
R sends 2 to 3.
S sends 3 to 2.
So we get (2,2).
Start with 3:
R sends 3 to 1.
S sends 1 to 3.
So we get (3,3).
Answer:
S ∘ R = {(1,1), (2,2), (3,3)}
Find R squared.
Explanation:
R squared means R composed with R.
Do R, then R again.
R sends:
1 to 2, then 2 to 3, so (1,3)
2 to 3, then 3 to 1, so (2,1)
3 to 1, then 1 to 2, so (3,2)
Answer:
R^2 = {(1,3), (2,1), (3,2)}
Find R cubed.
Explanation:
R is a cycle:
1 goes to 2,
2 goes to 3,
3 goes to 1.
After three steps, every element returns to itself.
Answer:
R^3 = {(1,1), (2,2), (3,3)}
Memory rule:
For S ∘ R, do R first, then S.
Follow the arrows.
QUESTION 9: Relation Properties
Let A = {1, 2, 3, 4}
For R = {(1,1), (2,2), (3,3), (4,4)}, decide whether it is reflexive, symmetric, antisymmetric, and transitive.
Explanation:
Reflexive means every element has a loop. Since (1,1), (2,2), (3,3), and (4,4) are all there, it is reflexive.
Symmetric means if (a,b) is there, then (b,a) is there. Loops reverse to themselves, so it is symmetric.
Antisymmetric means there are no two-way pairs between different elements. Since there are only loops, it is antisymmetric.
Transitive means if (a,b) and (b,c), then (a,c). Since there are only loops, transitivity holds.
Answer:
Reflexive: yes
Symmetric: yes
Antisymmetric: yes
Transitive: yes
Now consider R = {(1,2), (2,1), (3,3)}.
Explanation:
Reflexive? No, because we are missing (1,1), (2,2), and (4,4).
Symmetric? Yes, because (1,2) and (2,1) both exist, and (3,3) reverses to itself.
Antisymmetric? No, because (1,2) and (2,1) both exist while 1 is not equal to 2.
Transitive? No, because (1,2) and (2,1) would require (1,1), but (1,1) is missing.
Answer:
Reflexive: no
Symmetric: yes
Antisymmetric: no
Transitive: no
Memory rule:
Reflexive: all loops.
Symmetric: arrows go both ways.
Antisymmetric: no two-way arrows between different vertices.
Transitive: shortcut arrow must exist.
QUESTION 10: Matrix Multiplication
Let:
A = [[1, 2],
[3, 4]]
B = [[0, 1],
[2, 3]]
Find AB.
Explanation:
Use row times column.
First entry:
Row 1 of A times column 1 of B:
1(0) + 2(2) = 0 + 4 = 4
Second entry:
Row 1 of A times column 2 of B:
1(1) + 2(3) = 1 + 6 = 7
Third entry:
Row 2 of A times column 1 of B:
3(0) + 4(2) = 0 + 8 = 8
Fourth entry:
Row 2 of A times column 2 of B:
3(1) + 4(3) = 3 + 12 = 15
Answer:
AB = [[4, 7],
[8, 15]]
Now find BA.
First entry:
0(1) + 1(3) = 3
Second entry:
0(2) + 1(4) = 4
Third entry:
2(1) + 3(3) = 2 + 9 = 11
Fourth entry:
2(2) + 3(4) = 4 + 12 = 16
Answer:
BA = [[3, 4],
[11, 16]]
Are AB and BA equal?
No. Matrix multiplication is not usually commutative.
QUESTION 11: Boolean Matrix Multiplication
Let:
A = [[1, 0, 1],
[0, 1, 1]]
B = [[1, 0],
[0, 1],
[1, 1]]
Find the Boolean product A ⊙ B.
Explanation:
Boolean multiplication uses AND instead of multiplication, and OR instead of addition.
Entry 1,1:
(1 AND 1) OR (0 AND 0) OR (1 AND 1)
= 1 OR 0 OR 1
= 1
Entry 1,2:
(1 AND 0) OR (0 AND 1) OR (1 AND 1)
= 0 OR 0 OR 1
= 1
Entry 2,1:
(0 AND 1) OR (1 AND 0) OR (1 AND 1)
= 0 OR 0 OR 1
= 1
Entry 2,2:
(0 AND 0) OR (1 AND 1) OR (1 AND 1)
= 0 OR 1 OR 1
= 1
Answer:
A ⊙ B = [[1, 1],
[1, 1]]
QUESTION 12: Adjacency Matrix
Given vertices A, B, C, D and edges:
AB, AC, BD, CD, DA
Find the adjacency matrix using the order A, B, C, D.
Explanation:
Make a table where rows and columns are A, B, C, D.
Put 1 if there is an edge.
Put 0 if there is no edge.
A is connected to B, C, and D:
A row is 0, 1, 1, 1
B is connected to A and D:
B row is 1, 0, 0, 1
C is connected to A and D:
C row is 1, 0, 0, 1
D is connected to A, B, and C:
D row is 1, 1, 1, 0
Answer:
[[0, 1, 1, 1],
[1, 0, 0, 1],
[1, 0, 0, 1],
[1, 1, 1, 0]]
Find the degree of each vertex.
Explanation:
Degree means number of edges touching the vertex.
A touches B, C, D, so deg(A) = 3.
B touches A, D, so deg(B) = 2.
C touches A, D, so deg(C) = 2.
D touches A, B, C, so deg(D) = 3.
Answer:
deg(A) = 3
deg(B) = 2
deg(C) = 2
deg(D) = 3
Is the graph connected?
Yes, because every vertex can reach every other vertex.
QUESTION 13: Graph Powers and Paths
Given adjacency matrix:
A = [[0, 1, 1],
[1, 0, 1],
[1, 1, 0]]
Find A squared.
Explanation:
A squared tells us the number of paths of length 2 between vertices.
After multiplying A by A, we get:
A^2 = [[2, 1, 1],
[1, 2, 1],
[1, 1, 2]]
Find how many paths of length 2 go from vertex 1 to vertex 3.
Explanation:
Look at A squared, row 1, column 3.
The entry is 1.
Answer:
There is 1 path of length 2 from vertex 1 to vertex 3.
Memory rule:
A^2 means paths of length 2.
A^3 means paths of length 3.
Row = starting vertex.
Column = ending vertex.
QUESTION 14: Bipartite Graphs
Decide if C4 is bipartite.
Explanation:
C4 is a cycle with 4 vertices. Even cycles are bipartite.
Answer:
C4 is bipartite.
Decide if C5 is bipartite.
Explanation:
C5 is a cycle with 5 vertices. Odd cycles are not bipartite.
Answer:
C5 is not bipartite.
Decide if K2,3 is bipartite.
Explanation:
K2,3 is complete bipartite by definition. It already has two groups: one group has 2 vertices, and the other group has 3 vertices.
Answer:
K2,3 is bipartite.
Decide if C3 is bipartite.
Explanation:
C3 is a triangle, which is an odd cycle. Odd cycles are not bipartite.
Answer:
C3 is not bipartite.
Memory rule:
Even cycle equals bipartite.
Odd cycle equals not bipartite.
QUESTION 15: Euler Path and Euler Circuit
For the degree sequence 2, 2, 2, 2, decide if the graph has an Euler circuit, Euler path only, or neither.
Explanation:
All vertices have even degree. If all vertices are even, the graph has an Euler circuit.
Answer:
Euler circuit.
For the degree sequence 1, 2, 2, 3.
Explanation:
Odd degrees are 1 and 3. There are exactly two odd vertices. That means Euler path only.
Answer:
Euler path only.
For the degree sequence 1, 1, 3, 3.
Explanation:
All four degrees are odd. More than two odd vertices means neither Euler path nor Euler circuit.
Answer:
Neither.
For the degree sequence 2, 3, 3, 4.
Explanation:
Odd degrees are 3 and 3. There are exactly two odd vertices.
Answer:
Euler path only.
Memory rule:
Zero odd vertices means Euler circuit.
Two odd vertices means Euler path only.
More than two odd vertices means neither.
QUESTION 16: Weighted Graph and Minimum Spanning Tree
Given weighted edges:
AB = 4
AC = 2
BC = 1
BD = 5
CD = 8
CE = 10
DE = 2
BE = 6
Use Kruskal’s algorithm to find the minimum spanning tree.
Explanation:
Kruskal’s algorithm sorts all edges from smallest to largest.
Sorted edges:
BC = 1
AC = 2
DE = 2
AB = 4
BD = 5
BE = 6
CD = 8
CE = 10
Now add edges one by one, but do not create a cycle.
Add BC = 1.
Add AC = 2.
Add DE = 2.
Skip AB = 4 because A, B, and C are already connected, so AB would create a cycle.
Add BD = 5 because it connects the ABC group to the DE group.
Now all vertices are connected.
MST edges:
BC, AC, DE, BD
Total weight:
1 + 2 + 2 + 5 = 10
Answer:
Minimum spanning tree has total weight 10.
Now use Prim’s algorithm.
Explanation:
Prim’s algorithm starts at one vertex and grows the tree by choosing the smallest edge to a new vertex.
Start at A.
The smallest edge from A is AC = 2.
Now we have A and C.
The smallest edge connecting A or C to a new vertex is CB = 1.
Now we have A, B, C.
The smallest edge connecting A, B, or C to a new vertex is BD = 5.
Now we have A, B, C, D.
The smallest edge connecting to E is DE = 2.
Now all vertices are connected.
MST edges:
AC, CB, BD, DE
Total weight:
2 + 1 + 5 + 2 = 10
Answer:
Prim’s algorithm gives the same minimum spanning tree weight, 10.
FINAL EXAM STRATEGY
When you see a logic translation question, circle the keywords:
everyone, some, not, and, or, if.
When you see inference rules, match the pattern.
When you see sets, do parentheses first.
When you see summations, check if it is sum of i, sum of i squared, or geometric.
When you see counting, ask: does order matter?
If yes, permutation.
If no, combination.
When you see relation properties, check in this order:
reflexive, symmetric, antisymmetric, transitive.
When you see relation composition, follow arrows.
When you see matrices, do row times column.
When you see adjacency matrix, put 1 for edge and 0 for no edge.
When you see Euler, count odd degrees.
When you see bipartite, look for odd cycles.
When you see weighted graph, use Kruskal or Prim and avoid cycles.
That is the core COEN240 final review. The exam is about recognizing the question type and applying the right steps.