Recitation 4

Recitation notes for the week of October 5, 2026.

Homework 3 reminders

Homework 3 is due Friday, October 9, 2026, at 11:30 p.m. Submit Q1(a), Q1(b), Q2(a), and Q2(b) as separate PDFs to their corresponding UBLearns links. Submit Q3 code to Autolab. See the homework page for the full submission instructions.

Homework 3, Question 1: A Dam Good Ice-Cream Party

An assignment

Beatrice the beaver is organizing an ice-cream party for $p\ge 1$ beavers. There are $f$ pairs of friends among the $p(p-1)/2$ possible pairs. Friendship is mutual, and the friendship graph may be disconnected.

An assignment gives each beaver between $1$ and $p$ scoops of a single flavor, chosen from $p$ flavors. Each beaver must receive a unique combination of scoop count and flavor: two beavers may share a scoop count or a flavor, but not both.

Represent the assignment as a $p\times p$ table. Row $i$ represents $i$ scoops, and column $j$ represents flavor $j$. Each beaver appears in exactly one cell; an empty cell means that combination is unassigned.

Admissible assignment

An assignment is called admissible if:

  1. For every pair of friends $(b_1,b_2)$, their scoop counts differ by at most one.
    Friends may receive equal scoop counts or differ by one scoop. Their flavors do not affect this condition.
  2. At least one beaver receives exactly one scoop.
  3. The assignment satisfies the distance compatible property.
    For every beaver who receives one scoop, every beaver at a defined friendship distance $d$ from that beaver must receive exactly $d+1$ scoops. Friendship distance is the length of a shortest friendship path.

Which pairs does distance compatibility apply to?

It applies separately to every one-scoop beaver and every beaver reachable from that beaver through friendships, including any other one-scoop beaver. It is not a condition on every pair of beavers.

If two beavers lie in different connected components, their friendship distance is undefined. The homework does not require every component to contain a one-scoop beaver. All beavers must still satisfy the other assignment requirements.

Example 1

Two assignments for three beavers are shown below. In each table, rows from top to bottom represent $1$, $2$, and $3$ scoops; columns from left to right represent flavors $1$, $2$, and $3$.

Friendships = { (A, B), (B, C) }
            +--+---+--+
            |  | A |  |
            +--+---+--+
            |  | B |  |
            +--+---+--+
            |  | C |  |
            +--+---+--+

            +---+---+---+
            |   | B |   |
            +---+---+---+
            | A |   | C |
            +---+---+---+
            |   |   |   |
            +---+---+---+

Both assignments are admissible. Each beaver appears once, and no two beavers share a scoop/flavor combination.

How the first assignment satisfies the three properties:

  1. A and B differ by one scoop, as do B and C. Thus, every pair of friends has scoop counts differing by at most one.
  2. A receives one scoop.
  3. B has friendship distance $1$ from A and receives $2$ scoops. C has friendship distance $2$ from A and receives $3$ scoops.

How the second assignment satisfies the three properties:

  1. B receives one scoop, while A and C each receive two. Every pair of friends differs by one scoop.
  2. B receives one scoop.
  3. A and C each have friendship distance $1$ from B and each receive $2$ scoops, of different flavors.

    Why may A and C receive the same number of scoops?

    A and C have friendship distance $2$ from each other, but neither receives one scoop. Distance compatibility therefore imposes no condition directly between A and C. Their different flavors keep their scoop/flavor combinations distinct.

Example 2

Again, rows represent scoop counts and columns represent flavors, both starting at $1$.


                        Friendships = { (A,D),(C,B),(A,C),(B,E) }
                        +---+---+---+--+--+
                        |   | A |   |  |  |
                        +---+---+---+--+--+
                        | C |   | D |  |  |
                        +---+---+---+--+--+
                        |   | B |   |  |  |
                        +---+---+---+--+--+
                        |   | E |   |  |  |
                        +---+---+---+--+--+


                        +---+---+---+--+--+
                        |   | C |   |  |  |
                        +---+---+---+--+--+
                        | A |   | B |  |  |
                        +---+---+---+--+--+
                        |   | D | E |  |  |
                        +---+---+---+--+--+

Both assignments are admissible. There are $5\times 5$ possible scoop/flavor combinations; empty rows at the bottom of each table are omitted from these illustrations.

How the first assignment satisfies the three properties:

  1. The pairs of friends are A and D, C and B, A and C, and B and E. Each pair differs by one scoop.
  2. A receives one scoop.
  3. C and D have friendship distance $1$ from A and receive $2$ scoops each. B has distance $2$ and receives $3$ scoops. E has distance $3$ and receives $4$ scoops.

How the second assignment satisfies the three properties:

  1. C receives one scoop; A and B receive two; D and E receive three. Every pair of friends differs by one scoop.
  2. C receives one scoop.
  3. A and B have friendship distance $1$ from C and receive $2$ scoops each. D and E have distance $2$ and receive $3$ scoops each.

Q1 Part (a)

The Problem

For part (a), formally define the input, an assignment, and admissibility in terms of a graph.

Formalizing the problem

  • How do we represent the beavers and friendships as a graph $G=(V,E)$?
    1. Beavers are the vertices, so $|V|=p$.
    2. An undirected edge $(i,k)\in E$ represents a friendship between beavers $i$ and $k$, so $|E|=f$. The graph need not be connected.
  • How do we define an assignment?
    • An assignment is a one-to-one function $s:V\to [p]^2$. If $s(u)=(r,c)$, beaver $u$ receives $r$ scoops of flavor $c$. Here, $[p]=\{1,2,\dots,p\}$.
    • The output table places beaver $u$ in cell $(r,c)$ and uses an empty marker in every unassigned cell.
  • What makes the assignment admissible?
    1. If $(i,k)\in E$, $s(i)=(r_i,c_i)$, and $s(k)=(r_k,c_k)$, then $|r_i-r_k|\le 1$.
      This condition concerns adjacent vertices (direct friends) and their scoop counts, regardless of flavor.
    2. There exist $u\in V$ and $c\in [p]$ such that $s(u)=(1,c)$.
      At least one beaver receives one scoop. This does not say that exactly one beaver must receive one scoop.
    3. Formalize the third property, distance compatible, yourself for part (a). Pay attention to every one-scoop beaver and to whether a friendship distance is defined.

Q1 Part (b)

Using part (a) or otherwise, design an algorithm that computes an admissible assignment and its $p\times p$ output table in $O(f+p^2)$ time, where $f=|E|$. Your algorithm must handle disconnected friendship graphs, including isolated beavers. Prove its correctness and justify its running time.

Think about the graph exploration algorithms you have seen in class. BFS and DFS are not interchangeable for every task. Note that $f\le p(p-1)/2$, so the required time bound is also $O(p^2)$.

Homework 3, Question 2

We first recall the question:

The Problem

A 4-clique in a graph $G=(V,E)$ is a set of four distinct vertices $\{u,v,w,x\}$ such that $(u,v),(v,w),(w,x),(x,u),(u,w),(v,x)\in E$. (Note that $G$ is undirected.) Let $n=|V|$ and $m=|E|$. In this problem, you will design a series of algorithms that, given a connected graph $G$ as input, list all the $4$-cliques in $G$. (It is fine to list one $4$-clique more than once.) We call this the 4-clique listing problem (duh!). You can assume that as input you are given $G$ in both the adjacency matrix and adjacency list formats. For this problem, you can also assume that $G$ is connected.

Sample Input/Output pair

Question 2, part (a)

The Problem

Present an $O(n^4)$ time algorithm to solve the $4$-clique listing problem. Only an algorithm idea is required for this part.

Algorithm Idea

Let us assume we have access to a function Check-if-4-clique that takes as input $G=(V,E)$ and four vertices $u,v,w,x\in V$ and outputs true if $\{u,v,w,x\}$ is a $4$-clique in $G$ and false otherwise.

Then the algorithm is simple: just go through all possible $n^4$ $4$-tuples $\{u,v,w,x\}$ and, if Check-if-4-clique$(G,u,v,w,x)$ outputs true, then we add $\{u,v,w,x\}$ to the output.

Duplicates

The above algorithm would output the same set $\{u,v,w,x\}$ $24$ times, but that is OK for this problem. As long as you (1) only output $4$-cliques; (2) output all $4$-cliques and (3) maintain the given time bound, you can have duplicates.

Exercise

Show that Check-if-4-clique can be implemented in $O(1)$ time.

Algorithm Details

Even though this is not needed for your HW submission, we write down the details of the $O(n^4)$ time algorithm (assuming access to Check-if-4-clique as a black box, of course):

                                    Let GL and GM be the adjacency list and adjacency matrix representation of G (both are input).
                                    # GL is an array of pointers to linked list. The indices to vertices are in GL.keys()

                                    #Get the set of vertices
                                    V = GL.keys()

                                    L = null

                                    #Cycle through all 4-tuples
                                    for u in V:
                                        for v in V:
                                            for w in V:
                                                for x in V:
                                                    if Check-if-4-clique(GM,u,v,w,x) == true:
                                                        Add {u,v,w,x} to L

                                    return L

Question 2, part (b)

The Problem

Present an $O(m^2)$ time algorithm to solve the $4$-clique listing problem.

A Comment

We conclude with a comment:

Homework 3, Question 3

The input is an undirected graph represented by adjacency lists and a starting vertex $s$. The graph may be disconnected. Return an array or list whose entry at index $u$ is the minimum distance from $s$ to vertex $u$, for vertex IDs $0,1,\dots,n-1$.

The starting vertex has distance $0$. Return -1 for every vertex unreachable from $s$. The homework gives a target running time of $O(m+n)$, where $m$ is the number of edges.

One useful property of BFS:

BFS and distance

Say we run BFS from node $s$ in graph $G=(V,E)$ and let the layers be denoted by $L_0,L_1,\dots$. If $u\in L_i$ for any $u\in V$ and $i\ge 0$, then the distance between $s$ and $u$ is exactly $i$. Vertices unreachable from $s$ do not appear in these layers. This is (3.3) in the textbook.

Please see the textbook for a proof of this claim.

Further Reading