Your weeks

Pick a week to open it. The bar on each card shows how many of its practice questions you have tried.

How to study with this guide

1. Read and play. Each week starts with a short lesson. Use the interactive tools to test your understanding before moving on.
2. Recall, then practise. Answer the recall questions from memory, then try the practice set. Hints come one at a time, and a solution unlocks only after you have tried.
3. Drill before the exam. Use the Exam Lab for unlimited new questions, then take a timed mock exam. The cheat sheet collects everything on one page.

1. Propositions

A proposition is a declarative sentence that is either true or false. It does not have to be true. It only has to have a truth value.

Tap each sentence to see the verdict.

Propositional variables are p, q, r, … The proposition that is always true is T, and the one that is always false is F.

2. The connectives

A compound proposition is built from smaller propositions with connectives. Choose a connective, flip p and q, and watch which row of the table you are in.

Inclusive vs exclusive or. "Students who have taken CS202 or Math120 may take this class" allows both, so it is ∨. "Soup or salad comes with this entrée" allows only one, so it is ⊕.

3. Implication

p → q is read "if p, then q". Here p is the hypothesis and q is the conclusion. Using the promise from the top of the page:

• Got 100% and got an A: promise kept.
• Got 100% and no A: promise broken. This is the only way to break it.
• Did not get 100%: the promise says nothing about this case, so it cannot be broken. The implication is true. We call this vacuously true.

So p → q is false in exactly one row: p true and q false. This is why a sentence like "If 1 + 1 = 3, then your grandma wears combat boots" counts as true in logic.

Different ways to say p → q

Biconditional

p ↔ q ("p if and only if q") is true when p and q have the same truth value. Try it in the connectives table above. It means the same as (p → q) ∧ (q → p).

4. Converse, inverse, contrapositive

Start from p → q. You can form three related statements.

Look at the columns. The contrapositive matches the original in every row. The converse and inverse do not, although they match each other.

Example. "If it rains, the ground is wet." The converse is "if the ground is wet, it rained", which can be false because a sprinkler might be on. The contrapositive, "if the ground is not wet, it did not rain", is always valid.

Slide example. "It raining is a sufficient condition for my not going to town" is r → ¬t. Converse: if I do not go to town, then it is raining. Inverse: if it is not raining, then I will go to town. Contrapositive: if I go to town, then it is not raining.

5. Truth-table lab

With n variables you need 2ⁿ rows, and one column for every sub-expression. The lab does that for you. Type an expression, or use the symbol buttons. Single lowercase letters are variables, and T and F are constants.

The lab also names each result as a tautology, a contradiction or a contingency. Week 2 explains those names and how to compare two statements.

6. Precedence and translation

Precedence

From highest to lowest: ¬, ∧, ∨, →, ↔. So p ∨ q → ¬r means (p ∨ q) → ¬r. If you want p ∨ (q → ¬r), you must write the brackets. The lab above shows you the fully bracketed form of whatever you type.

Translating English

Two steps from your slides: (1) identify the atomic propositions and give each a variable, (2) choose the connectives.

7. Common mistakes

• Thinking p → q is false when p is false. It is true.
• Reading "p only if q" as q → p.
• Claiming the converse or inverse is equivalent to the original. Only the contrapositive is.
• Forgetting that ∨ is inclusive unless ⊕ is stated.
• Leaving out brackets when precedence changes the meaning.
• Skipping rows. Always list all 2ⁿ rows systematically.

Where this goes next. Week 2 turns to logical equivalence: tautologies, De Morgan's Laws and proofs with named laws. Everything you learned here, especially the truth tables and p → q, is the machinery for it.

8. Active recall

Answer from memory in the box, then check. The check button unlocks once you have typed something.

9. Practice set

Three easy, four medium, three challenging. Write your attempt first. Hints come in three levels, and the full solution unlocks only after you have written an attempt. Use the truth-table lab to check your tables, but do the reasoning yourself.

10. Weekly checkpoint

Rate how you feel about each objective, then build your checkpoint.

1. Tautologies, contradictions, contingencies

Once you can build truth tables, look at the final column. Its pattern gives the statement a name.

• A tautology is always true, like p ∨ ¬p. Every row of the final column is T.
• A contradiction is always false, like p ∧ ¬p. Every row is F.
• A contingency is neither: sometimes true, sometimes false, like p.

Your slide's table for p: when p is T, ¬p is F, so p ∨ ¬p is T and p ∧ ¬p is F; the same happens when p is F. "Either it is raining or it is not" can never be false, so it is a tautology.

Classifier

Type any statement. The lab shows its truth table and names it.

2. Logical equivalence

Idea. Two statements that look different can say exactly the same thing. If they are always true together and false together, they are logically equivalent.

Slide example. ¬p ∨ q is equivalent to p → q:

The two highlighted columns match in all four rows, so the statements are equivalent.

Showing that statements are NOT equivalent

Your slides show that the converse and the inverse of p → q are not equivalent to p → q, while the contrapositive is. You only need one row where the columns differ to prove non-equivalence. Press the "vs converse" and "vs inverse" buttons in the checker at the top: the first differing row is highlighted.

3. De Morgan's Laws

Named after Augustus De Morgan (1806 to 1871). They tell you how to push a negation inside brackets.

Easy way to remember. When the ¬ moves inside the brackets, the connective flips: ∧ becomes ∨, and ∨ becomes ∧. Each part gets its own ¬.

In words (beyond the slides). "It is not true that I have both a pen and a ruler" means I am missing the pen or I am missing the ruler. "It is not true that I have a pen or a ruler" means I have neither: no pen and no ruler.

Your slide shows the second law in a truth table:

4. The key equivalences

These are the building blocks for proofs. A variable in any law can be replaced by an arbitrarily complex proposition. The right-hand column is a plain-words reading of each law (my wording, not from the slides).

Conditional statements (Table 7)

Biconditional statements (Table 8)

5. Proving equivalences with laws

Truth tables get huge (10 variables means 1,024 rows). Instead, show A ≡ B by writing a chain A ≡ A₁ ≡ … ≡ A_n ≡ B, where each step uses one named law.

Reading a proof. At every step ask: which law turned the line above into this line? If you cannot name it, you have not understood the step yet.

6. Common mistakes

• Pushing ¬ inside brackets without flipping ∧ and ∨.
• Claiming the converse or inverse is equivalent to p → q. Only the contrapositive is.
• Concluding "equivalent" after checking only some rows of a truth table.
• Using a law in a step without being able to name it.
• Applying a law to only part of a line and forgetting the rest of it.
• Writing ≡ between statements that are merely similar. Equivalent means equal in every row.
• Forgetting that T and F are propositions too: p ∧ T ≡ p, but p ∧ F ≡ F.

Where this goes next. The Chapter 1 summary slide lists predicate logic (the language of quantifiers) and proofs (rules of inference, proof methods, proof strategy). Rules of inference are tautologies written as arguments, so everything in this week is the machinery for them. I do not have those slides yet.

7. Active recall

Answer from memory in the box, then check. The check button unlocks once you have typed something.

8. Practice set

Three easy, four medium, three challenging. Write your attempt first. Hints come in three levels, and the solution unlocks only after you have written an attempt. Use the checker and classifier above to verify an answer, but do the reasoning yourself.

9. Weekly checkpoint

Rate how you feel about each objective, then build your checkpoint.

1. What is an algorithm?

Every algorithm begins with a clearly stated problem: a valid input goes in, and the desired output comes out. The first job is to state the problem precisely: what the input is, and what the output must be.

Example: the input is a finite list of integers, and the output is the largest integer in it.

Easy way to think about it (beyond the slides): an algorithm is like a recipe written so carefully that someone who cannot think, only obey, still gets the right dish. "Add salt to taste" is not precise enough. "Add 1 teaspoon of salt" is.

Three ways to write an algorithm down

• Structured English: numbered steps in plain sentences.
• Pseudocode: code-like steps that are not tied to any programming language. This is what we use most.
• Flowchart: boxes and arrows.

2. Reading pseudocode

Your pseudocode needs only three ideas: assignments, conditional statements and loops, all wrapped in a procedure.

3. Worked example: the maximum of a list

Idea. Keep a "champion so far". Start with the first number. Look at the next number. If it is bigger, it becomes the new champion. Repeat until the list ends.

Structured English

1. Set the temporary maximum equal to the first integer in the sequence.
2. Compare the next integer with the temporary maximum. If it is larger, set the temporary maximum equal to this integer.
3. Repeat the previous step if there are more integers. If not, stop.
4. When the algorithm stops, the temporary maximum is the largest integer.

Pseudocode, with a for loop and with a while loop

procedure max(a1, a2, …, an: integers)       procedure max(a1, a2, …, an: integers)
max := a1                                      max := a1
for i := 2 to n                                i := 2
    if max < ai then max := ai                while i ≤ n
return max {max is the largest element}              if max < ai then max := ai
                                                   i := i + 1
                                               return max {max is the largest element}

The trace from your slide: (10, 6, 8, 20, 2)

Try it. In the player at the top of the page, type a new list and predict each step before you press Next. That is the fastest way to learn tracing.

4. Properties of algorithms

A procedure only counts as an algorithm if it has these properties.

Definiteness also appears in your slide's max example and answers: each step must be precisely defined. For max, this holds because only assignments, a finite loop and conditional statements occur.

Property detective (from your slides)

Each procedure below is broken. Decide which property it lacks. If you get one wrong, I will ask you a smaller question first.

5. Three kinds of problem

• Searching: find the position of a particular element in a list.
• Sorting: put the elements of a list into increasing order.
• Optimization: find the best (maximum or minimum) value of some quantity over all possible inputs.

The rest of this page takes them in order.

6. Searching

The problem. Locate an element x in a list of distinct elements a₁, a₂, …, a_n, or decide that it is not there. The answer is the location i where x = a_i, or 0 if x is not in the list. Positions start at 1, so 0 can never be a real position, which is why it safely means "not found".

Our focus is two methods: linear search and binary search.

Linear search

Idea. Look at the first element, then the second, then the third, until you find x or run out of list. It is like scanning a class attendance list from the top to find one name.

procedure linear search(x: integer, a1, a2, …, an: distinct integers)
i := 1
while (i ≤ n and x ≠ ai)
    i := i + 1
if i ≤ n then location := i
else location := 0
return location {location is the subscript of the term that equals x, or 0 if x is not found}

From your slide: x = 30 in (10, 50, 30, 70) gives location 3. x = 40 in the same list gives location 0. Run both:

Binary search

Idea. This needs a list already in increasing order. Look at the middle element. If x is bigger, it can only be in the right half. Otherwise it is at the middle or in the left half. Keep halving. It is the "guess my number" game: guessing 50 out of 100 and being told higher or lower.

procedure binary search(x: integer, a1, a2, …, an: increasing integers)
i := 1 {i is the left endpoint of the interval}
j := n {j is the right endpoint of the interval}
while i < j
    m := ⌊(i + j)/2⌋
    if x > am then i := m + 1
    else j := m
if x = ai then location := i
else location := 0
return location

The symbol ⌊ ⌋ is the floor: round down to a whole number. For example ⌊(1 + 16)/2⌋ = ⌊8.5⌋ = 8.

Your slide searches for 19 in a 16-element list. Step through it, and watch the grey cells (outside the interval) fade out.

7. Sorting

To sort a list is to put its elements in increasing order. There are many sorting algorithms (binary, insertion, bubble, selection, merge, quick, tournament). Your slides work through two: bubble sort and insertion sort.

Bubble sort

Idea. Make several passes through the list. Whenever two neighbours are in the wrong order, swap them. Big values "bubble" to the right, so after pass 1 the largest is at the end, after pass 2 the two largest are at the end, and so on.

procedure bubblesort(a1, …, an: real numbers with n ≥ 2)
for i := 1 to n − 1
    for j := 1 to n − i
        if aj > aj+1 then interchange aj and aj+1
{a1, …, an is now in increasing order}

Why does the inner loop stop at n − i? After i − 1 passes the last i − 1 elements are already in place, so there is no need to compare them again. Try the slide example (3, 2, 4, 1, 5):

Insertion sort

Idea. Sort a hand of playing cards: pick up the next card and slide it into the right place among the cards you already hold. Your sorted section starts as just the first element and grows by one each round. Your slide notes that insertion sort uses a linear search to find the correct position.

procedure insertion sort(a1, …, an: real numbers with n ≥ 2)
for j := 2 to n
    i := 1
    while aj > ai
        i := i + 1
    m := aj
    for k := 0 to j − i − 1
        aj−k := aj−k−1
    ai := m
{Now a1, …, an is in increasing order}

Read it in three parts: (1) the while finds the position i, (2) m := aj saves the new element, (3) the inner for shifts elements right to make a gap, then ai := m drops the saved value into the gap.

8. Greedy algorithms

An optimization problem asks you to minimize or maximize something over all possible inputs. Examples from your slides: find the route between two cities with the smallest total mileage; encode messages using the fewest bits; connect network nodes using the least fibre.

A greedy algorithm solves such a problem by making the best-looking choice at each step. That does not always produce an optimal solution overall, but often it does. So after you pick a greedy rule, you either prove it is always optimal, or find a counterexample.

Making change

Problem. Make change for n cents with quarters (25), dimes (10), nickels (5) and pennies (1), using the fewest coins. Greedy rule: at each step take the largest coin that does not exceed what is left.

Slide example, n = 67: quarter (left 42), quarter (left 17), dime (left 7), nickel (left 2), penny (left 1), penny (left 0). That is 6 coins.

procedure change(c1, c2, …, cr: values of coins, where c1 > c2 > … > cr; n: a positive integer)
for i := 1 to r
    di := 0 {di counts the coins of denomination ci}
    while n ≥ ci
        di := di + 1 {add a coin of denomination ci}
        n := n − ci
{di counts the coins ci}

Greedy lab

Type any coin values and an amount. The lab runs the greedy algorithm and also searches for the true minimum.

9. Common mistakes

• Mixing up := (assign) and = (test).
• Starting the loop at the wrong place. In max, max := a1 and the loop starts at i := 2.
• Forgetting i := i + 1 inside a while loop, so it never ends.
• Running binary search on a list that is not sorted.
• Forgetting to round the midpoint down: m := ⌊(i + j)/2⌋.
• In bubble sort, running the inner loop to n instead of n − i.
• In linear search, forgetting that "not found" returns 0.
• Believing a greedy algorithm is always optimal.
• Tracing too fast. Write down the variables after every step.

Connection to Week 1. Every if test and every loop condition is a proposition that is true or false. Reading i ≤ n and x ≠ ai uses ∧ and ¬ exactly as you learned in propositional logic.

10. Active recall

Answer from memory in the box, then check. The check button unlocks once you have typed something.

11. Practice set

Three easy, four medium, three challenging. Write your attempt first. Hints come in three levels, and the solution unlocks only after you have written an attempt. You can use the players above to check a trace, but do the tracing yourself first.

12. Weekly checkpoint

Rate how you feel about each objective, then build your checkpoint.

1. What is a relation?

Big picture. A relation says which things are connected to which. "Student s is enrolled in course c", "x divides y" and "x ≤ y" are all relations. In maths we store the connection as a set of ordered pairs.

An ordered pair (a, b) has an order: (1, 2) is not the same pair as (2, 1). The set of all possible pairs from A to B is A × B. A relation just picks some of them.

Slide example. Let A = {0, 1, 2} and B = {a, b}. Then R = {(0, a), (0, b), (1, a), (2, b)} is a relation from A to B. As a table, a × means "related":

Relations on a set

When A = B we say R is a relation on A: a subset of A × A. All four properties in this chapter are about relations on a set.

Slide example. Let A = {1, 2, 3, 4} and R = {(a, b) | a divides b}. The pairs are (1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), (4,4). Press a divides b in the explorer to see this exact relation.

2. Reflexive

Idea. Everything is related to itself. Think of "has the same age as": you are always the same age as yourself.

How to check. In the grid, the whole diagonal must be filled. Write down every pair (a, a) for the set, then tick each one off. One missing pair is enough to fail.

Slide example. R = {(a, a), (b, b)} on X = {a, b} is reflexive.

3. Symmetric and antisymmetric

Symmetric: a two-way street

Idea. If a is related to b, then b is related to a. "Is a classmate of" works that way.

How to check. For every pair (x, y), look for its reverse (y, x). In the grid, the picture must be a mirror image across the diagonal. A loop (a, a) is its own reverse, so loops never break symmetry.

Slide example. R = {(1,2), (2,1), (3,2), (2,3)} on {1, 2, 3} is symmetric. (The explorer has a button for it.)

Antisymmetric: no two-way streets between different elements

Idea. Two different elements are never related in both directions. "Is at most as tall as" works that way: if you are at most as tall as me and I am at most as tall as you, we must be the same height.

How to check. Ignore the loops. For every pair (x, y) with x ≠ y, the reverse (y, x) must not be in R.

Slide example. R = {(x, y) ∈ N | x ≤ y} is antisymmetric, because x ≤ y and y ≤ x imply x = y.

These four examples are mine, not from your slides. Type each into the explorer to check.

4. Transitive

Idea. "A friend of a friend is a friend": if you can get from a to b and from b to c, you can get from a to c directly. "Is taller than" works that way.

How to check, step by step.

1. Take a pair (a, b) in R.
2. Find every pair that starts with b, say (b, c).
3. For each one, the shortcut (a, c) must be in R. If it is missing, R is not transitive.
4. Repeat for every pair in R.

Slide example. R = {(1,2), (2,3), (1,3)} on {1, 2, 3} is transitive. The only chain is (1,2),(2,3), and its shortcut (1,3) is there.

procedure is symmetric(R: a set of pairs)
for each pair (a, b) in R
    if (b, a) is not in R then return false
return true

5. Combining and composing relations

Combining

A relation is a set, so you can combine two relations with set operations: R₁ ∪ R₂ (in either), R₁ ∩ R₂ (in both), R₁ − R₂ (in R₁ but not R₂) and R₂ − R₁.

Slide example. R₁ = {(1,1), (2,2), (3,3)} and R₂ = {(1,1), (1,2), (1,3), (1,4)} give:

Edit the boxes to try your own. Write pairs like (1,2), (2,3).

Composition

Idea. Composition chains two relations into a two-step journey. First take a step with R₁, then a step with R₂. Whenever that journey is possible from x to z, the pair (x, z) is in the composite.

Reading order. R₂ ∘ R₁ is read right to left: R₁ acts first. (The slide's figure labels the answer R₂ ∘ R₁ = {(b, x), (b, z)}, while the slide's text layer shows R₁ ∘ R₂. Follow the figure and the definition: first R₁, then R₂.)

How to compute. For each pair (x, y) in R₁, find every pair in R₂ that starts with that same y, say (y, z). Each match gives (x, z). The middle element y is used up and does not appear in the answer.

6. Common mistakes

• Calling a relation reflexive when it has loops only for the elements that appear. Check every element of A.
• Thinking antisymmetric means "not symmetric". They are different questions.
• Saying (a, a) breaks antisymmetry. It does not: a = a.
• Checking only some chains for transitivity. Check every pair against every pair that starts where it ends.
• Treating (a, b) and (b, a) as the same pair. They are different.
• Forgetting vacuous truth: with no chains, a relation is transitive.
• Reading R₂ ∘ R₁ left to right.

Connections. Every definition above is an implication (Week 1). Antisymmetry has the form (p ∧ q) → r, and its contrapositive says: if x ≠ y then not both (x, y) and (y, x) are in R. Checking a property is an algorithm (Week 3), and next week you will see these properties in matrices and graphs.

7. Active recall

Answer from memory in the box, then check. The check button unlocks once you have typed something.

8. Practice set

Three easy, four medium, three challenging. Many come straight from your slide exercises. Write your attempt first. Hints come in three levels, and the solution unlocks only after you have written an attempt. You can use the explorer and calculators above to check an answer, but work it out yourself first.

9. Weekly checkpoint

Rate how you feel about each objective, then build your checkpoint.

1. Representing relations with matrices

Big picture. A table of 1s and 0s can hold a whole relation. A 1 means "related", a 0 means "not related". It is the grid from Week 4, written as numbers.

Reading it. Row i is the first element, column j is the second element. The entry in row i, column j answers: is a_i related to b_j? The elements can be listed in any order, but when A = B use the same order for rows and columns.

Slide example 1. A = {1, 2, 3}, B = {1, 2}, and R holds (a, b) when a > b. Then R = {(2,1), (3,1), (3,2)} and:

Going the other way: matrix to pairs

Slide example 2 gives a matrix and asks for the pairs. The tool below does that. Rows are separated by new lines, entries by spaces.

Properties straight from the matrix

For a relation on a set (a square matrix), your slides give three quick tests:

• Reflexive if all entries on the main diagonal are 1.
• Symmetric if and only if m_ij = 1 whenever m_ji = 1. Picture: the matrix is a mirror image across the diagonal.
• Antisymmetric if and only if m_ij = 0 or m_ji = 0 whenever i ≠ j. Picture: no pair of 1s in mirror positions off the diagonal.

Slide example 3. M_R = [[1,1,0],[1,1,1],[0,1,1]]. The diagonal is all 1, so R is reflexive. The matrix equals its mirror image, so R is symmetric. And m₁₂ and m₂₁ are both 1, so R is not antisymmetric. (Press "Slide matrix example 3" in the tool at the top.)

2. Representing relations with digraphs

Big picture. Draw each element as a dot and each pair (a, b) as an arrow from a to b. It is the most visual way to see a relation.

Slide example 1. The digraph with vertices a, b, c, d and edges (a,b), (a,d), (b,b), (b,d), (c,a), (c,b), (d,b) is what the tool at the top shows when it loads. Notice the loop at b, and the two-way pair b ↔ d.

Slide example 2. The ordered pairs of the slide's second digraph are (1,3), (1,4), (2,1), (2,2), (2,3), (3,1), (3,3), (4,1), (4,3). Press "Slide digraph example 2" to draw them.

Reading properties from a digraph

3. Equivalence relations

Big picture. An equivalence relation is a precise version of "is the same kind as". "Has the same birthday month as", "lives in the same city as" and "has the same remainder when divided by 3" all sort things into groups of look-alikes.

Why these three? Reflexive: everything is the same kind as itself. Symmetric: if a is the same kind as b, then b is the same kind as a. Transitive: if a matches b and b matches c, then a matches c.

Try it. Press "Same remainder mod 3" in the tool at the top. It shows the relation a ∼ b if a and b leave the same remainder when divided by 3 on {1, …, 6}: the matrix, the digraph, and a verdict that it is an equivalence relation, with its classes listed. Then press "a divides b". It fails: which property breaks?

Equivalence classes

Let A be a nonempty set and ∼ an equivalence relation on A. The equivalence class of a, written [a] and read "bracket a", is the set of all elements of A that are equivalent to a. (The formula did not show in my copy of your slide, so this is the standard definition.) Your slide lists three facts:

• For each a ∈ A, a ∈ [a]. (Because ∼ is reflexive.)
• For each a, b ∈ A, a ∼ b if and only if [a] = [b].
• For each a, b ∈ A, [a] = [b] or [a] ∩ [b] = ∅. Two classes are either identical or completely separate.

In the mod 3 example, [1] = [4] = {1, 4}, [2] = [5] = {2, 5} and [3] = [6] = {3, 6}. Three classes, no overlaps.

Partitions

Picture. Cut a cake into pieces: no piece is empty, no two pieces overlap, and together they make the whole cake. The equivalence classes of an equivalence relation on A form a partition of A.

Partition checker

Type a set and a collection of subsets in braces. The checker tests the three conditions one by one.

4. Common mistakes

• Reading a matrix with rows and columns swapped. Row = first element.
• Calling a matrix antisymmetric because it is not symmetric. Test the mirror positions.
• Forgetting that the diagonal must be all 1s for reflexive.
• In a digraph, forgetting a loop at one vertex when checking reflexive.
• Checking transitivity by eye and missing a two-step path.
• Claiming an equivalence relation when one of the three properties fails. Name the pair that breaks it.
• Listing a class twice. [1] and [4] in the mod 3 example are the same class, {1, 4}.
• Calling something a partition when a block is empty, two blocks overlap, an element is missing, or an extra element appears.

Connections. Matrices and digraphs are two pictures of the pairs from Week 4. Equivalence relations combine three of the Week 4 properties. The partition conditions use set operations (∩, ∪, ∅) you already know, and "if and only if" is the biconditional from Week 1.

5. Active recall

Answer from memory in the box, then check. The check button unlocks once you have typed something.

6. Practice set

Three easy, four medium, three challenging. Several come from your slide exercises. Write your attempt first. Hints come in three levels, and the solution unlocks only after you have written an attempt. Use the tools above to check an answer, but work it out yourself first.

7. Weekly checkpoint

Rate how you feel about each objective, then build your checkpoint.

1. Graphs and graph terminology

Big picture. A graph is a set of dots (vertices) joined by lines (edges). Road maps, social networks and computer networks are all graphs. Last week a digraph pictured a relation; this week graphs are the main object.

Kinds of graph

• A simple graph: each edge connects two different vertices, and no two edges connect the same pair.
• A multigraph may have multiple edges between the same two vertices. If m edges connect u and v, the edge {u, v} has multiplicity m.
• A loop is an edge from a vertex to itself. A pseudograph may have loops as well as multiple edges.
• A simple directed graph has no loops and no multiple directed edges. A directed multigraph may have multiple directed edges (m edges from u to v: (u, v) has multiplicity m).

Adjacent, neighbourhood, degree

• Adjacent (neighbours): u and v are adjacent if an edge e joins them. The edge e is incident with u and v.
• Neighbourhood N(v): the set of all neighbours of v. For a set A of vertices, N(A) is the union of N(v) over all v in A.
• Degree deg(v): the number of edges incident with v, where a loop counts two.

Slide example. Press "Slide graph G" in the lab: deg(a) = 2, deg(b) = deg(c) = deg(f) = 4, deg(d) = 1, deg(e) = 3, deg(g) = 0, and N(g) = ∅ (g is isolated). Then press "Slide graph H": the loop at b adds 2, so deg(b) = 6, and b is in its own neighbourhood: N(b) = {a, b, c, d, e}.

In-degree and out-degree

Try it. Press "Slide adjacency list (directed)" in the lab. It has 12 edges, so the in-degrees add up to 12 and so do the out-degrees.

2. Special types of graphs

• Complete graph K_n: n vertices with exactly one edge between each pair of different vertices.
• Cycle C_n (n ≥ 3): vertices v₁, …, v_n and edges {v₁, v₂}, {v₂, v₃}, …, {v_n−1, v_n}, {v_n, v₁}.
• Wheel W_n (n ≥ 3): a cycle C_n plus one extra vertex joined to each of the n vertices.
• Bipartite graph: a simple graph whose vertices split into two disjoint sets V₁ and V₂ so that every edge joins a vertex of V₁ to a vertex of V₂. Same thing: you can colour the vertices red and blue with no edge joining two vertices of the same colour.
• Complete bipartite graph K_m,n: V₁ has m vertices, V₂ has n vertices, and every vertex of V₁ is joined to every vertex of V₂.
• Union G₁ ∪ G₂: the simple graph with vertex set V₁ ∪ V₂ and edge set E₁ ∪ E₂.

Slide example (bipartite). To show a graph is not bipartite, try the colouring and find a clash. On the slide, colouring a red forces its neighbours f and b to be blue, but f and b are adjacent. Any triangle does this, so K₃ is not bipartite.

Special graph drawer

3. Representing graphs

Big picture. A computer cannot store a drawing, so we store the graph as a list or a table. You should be able to go from a drawing to each representation and back.

Adjacency lists

An adjacency list (for a graph with no multiple edges) lists, for each vertex, the vertices adjacent to it. For a directed graph, list each initial vertex with its terminal vertices (where its arrows go).

Your slide tables. Press the two "Slide adjacency list" buttons in the lab to see the graphs they describe.

Adjacency matrices

• For a simple graph the matrix is symmetric (a_ij = a_ji) and the diagonal is all 0 (no loops).
• With multiple edges, a_ij is the number of edges between v_i and v_j. A loop at v_i puts a 1 at position (i, i) (more loops, a bigger number).
• For a directed graph, a_ij is the number of edges from v_i to v_j: row = start, column = end. It need not be symmetric.
• The matrix depends on the order of the vertices. Use the order the question gives (often alphabetical).

Slide example. Press "Slide pseudograph matrix". With order a, b, c, d the matrix is [[0,3,0,2],[3,0,1,1],[0,1,1,2],[2,1,2,0]]: three edges between a and b, one loop at c.

Incidence matrices

Rows are vertices, columns are edges. Each column of a normal edge has exactly two 1s; a loop's column has a single 1; multiple edges give identical columns. The lab numbers the edges in the order you type them and shows the incidence matrix for undirected graphs.

4. Connectivity

Big picture. A path is a walk along edges from vertex to vertex. Connectivity asks: can you get from any vertex to any other?

• The length is the number of edges (one less than the number of vertices in the list).
• A circuit begins and ends at the same vertex (u = v) and has length greater than 0.
• A path or circuit is simple if it does not use the same edge more than once.

Slide examples (graph "Slide paths example"): a, d, c, f, e is a simple path of length 4; d, e, c, a is not a path because e and c are not adjacent; b, c, f, e, b is a circuit of length 4; a, b, e, d, a, b is a path of length 5 that is not simple (it uses {a, b} twice). Check them below.

Path checker

Connected components

The lab at the top lists the components. "Slide graph G" has two: {a, b, c, d, e, f} and the lonely {g}.

5. Shortest paths: Dijkstra's algorithm

Big picture. In a weighted graph each edge has a number (a distance, a cost, a time). A shortest-path algorithm finds the minimum total cost from a source vertex to the other vertices. Dijkstra's algorithm finds the shortest paths from the source to all the other vertices.

The method by hand

1. Give the source distance 0 and every other vertex distance ∞.
2. Pick the unfinished vertex with the smallest distance and finalise it: its distance will not change again.
3. For each neighbour v of that vertex u that is not finalised, if dist(u) + w(u, v) < dist(v), replace dist(v) and remember that the best way to v comes from u.
4. Repeat steps 2 and 3 until every vertex is finalised. Follow the "comes from" links backwards to read each path.

Slide example. The tool below starts with the slide graph (vertices 0 to 8, source 0). Your slide's answer is 0 4 12 19 21 11 9 8 14, for example 0 → 7 → 6 → 5 → 4 = 8 + 1 + 2 + 10 = 21. The edge from 3 to 4 has weight 9, which does not show in the slide's picture.

6. Common mistakes

• Counting a loop as 1 in an undirected degree. It counts 2. (In a directed graph a loop adds 1 to in-degree and 1 to out-degree.)
• Mixing up in-degree and out-degree. In = arrows arriving, out = arrows leaving.
• Writing a 1 instead of the number of edges in the adjacency matrix of a multigraph.
• Writing a 2 on the diagonal for one loop. In the adjacency matrix a single loop is a 1.
• Reading a directed adjacency matrix the wrong way round. Row = start of the arrow, column = end.
• Using a different vertex order from the question. Keep the order you are given.
• Calling a path's length the number of vertices. Length = number of edges.
• In Dijkstra, finalising a vertex that is not the smallest, or forgetting to update a neighbour when a shorter route appears.
• Calling a graph bipartite without showing the two sets, or calling it not bipartite without pointing to the clash.

Connections. A directed graph is the digraph of a relation from Week 5, and the adjacency matrix of a simple directed graph is the relation's zero-one matrix. The neighbourhood N(A) is a union of sets, and Dijkstra is a greedy algorithm like those in Week 3: it always takes the closest unfinished vertex.

7. Active recall

Answer from memory in the box, then check. The check button unlocks once you have typed something.

8. Practice set

Three easy, four medium, three challenging. Most are your Tutorial 5 questions. Write your attempt first. Hints come in three levels, and the solution unlocks only after you have written an attempt. You can check an answer by typing the edges into the graph lab or the Dijkstra tool, but work it out yourself first.

9. Weekly checkpoint

Rate how you feel about each objective, then build your checkpoint.

1. How each tutorial question type works

Your tutorial and coursework sheets keep reusing a small set of question types. Here is the method for each one, in a few steps. Open a card, then try the matching question type above.

Logic

Algorithms

Relations

Graphs (see the next section)

2. Graph basics and tools

For the full lessons on graphs (Chapter 4), open Week 6 · Graphs. This is a quick summary with the two tools.

• A graph has vertices and edges. In a directed graph each edge is an arrow from one vertex to another. A multigraph allows several edges between the same two vertices, and a loop is an edge from a vertex to itself.
• Undirected degree: the number of edge ends at the vertex, so a loop counts 2. The degrees add up to 2 × (number of edges).
• Directed: in-degree is the number of edges arriving, out-degree the number leaving, and a loop counts 1 for each. Both sums equal the number of edges.
• Adjacency list: each vertex with the vertices it is joined to. Adjacency matrix: row i, column j holds the number of edges from i to j (for an undirected graph the matrix is symmetric, and a loop gives a 1 on the diagonal).

Graph lab

Type edges like a-b, b-c, c-c. Tick "directed" to read each edge as an arrow from the first vertex to the second. Parallel edges are allowed (type them twice). The lab draws the graph and gives the degrees, the adjacency list and the adjacency matrix.

Dijkstra tool

Type weighted edges like A-B:4, A-D:3 and a start vertex. The tool shows the table you would write by hand: one row per step, with the vertex being finalised.

3. Mock exam

A mixed set from all four topics, with no feedback until you submit, like the real thing. A timer runs while you work. After submitting you see the marks per topic, every solution, and your weakest topic.

4. Exam cheat sheet

One page of everything you need to recall, collected from all the weeks.

5. Your progress

Every question you answer is counted once (the first time you check it). Use the Practice buttons to drill your weak types.

Clear my exam-lab progress

The paper

Press "Start the timed attempt" above to open the paper and start the clock.