brand banner

Background

Recap of prereq knowledge for COMP 3804 (Fall 2025).

Updated · 6 min read · #comp3804 · #algorithms · #recurrences · #combinatorics · #probability

Background

Recap of prereq knowledge for COMP 3804 (Fall 2025).

COMP 3804 – Background Quiz

Question 1

log2128=log227=7

Question 2

log2𝑛 is the exponent to which the base 2 must be raised to produce the number n. In other words, it answers the question: “2 raised to what power equals n?”

Question 3

2𝑛. Use bit-strings to solve this problem (1 = element included in the set, 0 = not).

Bit-string representation of a subset

Question 4

𝑂(𝑛log𝑛).

This is the lower bound for comparison-based sorting algorithms, meaning that no comparison-based sorting algorithm can have a better average-case or worst-case time complexity than 𝑂(𝑛log𝑛).

Question 5

𝑂(log𝑛). Binary search if elements are sorted.

Question 6

𝑂(𝑛). Create a balanced BST by recursively choosing the middle element as the root.

Question 7

∑𝑘=1𝑛𝑘=𝑛(𝑛+1)2

Using geometry

Triangular arrangement of squares for the sum of integers

The total number of squares in the region highlighted in black is what we’re interested in counting. That is, length×height×12.

Using some 10-year-old’s sorcery

Gauss's pairing method for summing integers
Carl Friedrich Gauss

Question 8

Solve the following recurrence: 𝑇(1)=1 and for each 𝑛≥2 that is a power of two.

𝑇(𝑛)=2⋅𝑇(𝑛/2)+𝑛

𝑇(𝑛)=2⋅(2⋅𝑇(𝑛/22)+𝑛/2)⏟𝑇(𝑛/2)+𝑛=4⋅𝑇(𝑛/22)+𝑛+𝑛=4⋅𝑇(𝑛/4)+2𝑛𝑇(𝑛)=4⋅(2⋅𝑇(𝑛/42)+𝑛/4)⏟𝑇(𝑛/4)+2𝑛=8⋅𝑇(𝑛/8)+3𝑛𝑇(𝑛)=8⋅(2⋅𝑇(𝑛/82)+𝑛/8)⏟𝑇(𝑛/8)+3𝑛=16⋅𝑇(𝑛/16)+4𝑛⋮𝑇(𝑛)=2𝑘⋅𝑇(𝑛/2𝑘)+𝑘𝑛

Where 𝑘 is the number of times we have expanded the recurrence.

Remember, our goal is to express 𝑇(𝑛) only in terms of 𝑛 (eliminating the recursive definition). Because the base case is 𝑇(1), we can stop expanding when 𝑛/2𝑘=1, or when 𝑛=2𝑘. This means that 𝑘=log2(𝑛).

𝑇(𝑛)=2𝑘⋅𝑇(𝑛/2𝑘)+𝑘𝑛𝑇(𝑛)=2log2(𝑛)⋅𝑇(1)+𝑛⋅log2(𝑛)𝑇(𝑛)=𝑛⋅1+𝑛⋅log2(𝑛)

We can say that 𝑇(𝑛) is in 𝑂(𝑛log𝑛).

Question 9

Solve the following recurrence: 𝑇(1)=1 and for each 𝑛≥2 that is a power of two.

𝑇(𝑛)=𝑇(𝑛/2)+1

𝑇(𝑛)=𝑇(𝑛/2)+1=(𝑇((𝑛/2)/2)+1)⏟𝑇(𝑛/2)+1=𝑇(𝑛/4)+2𝑇(𝑛)=(𝑇((𝑛/4)/2)+1)⏟𝑇(𝑛/4)+2=𝑇(𝑛/8)+3⋮𝑇(𝑛)=𝑇(𝑛/2𝑘)+𝑘

Again, we stop expanding when 𝑛/2𝑘=1, or when 𝑛=2𝑘. This means that 𝑘=log2(𝑛).

𝑇(𝑛)=𝑇(𝑛/2𝑘)+𝑘=𝑇(𝑛/2log2(𝑛))+log2(𝑛)=1+log2(𝑛)

Concluding that 𝑇(𝑛) is in 𝑂(log𝑛).

Question 10

Let 𝐺 be a graph with 𝑛 vertices and 𝑛 edges. Can 𝐺 be a tree?

A tree is a connected graph with no cycles. A tree with 𝑛 vertices has exactly 𝑛−1 edges. Therefore, a graph with 𝑛 vertices and 𝑛 edges cannot be a tree, as it has one more edge than a tree would have.

Question 11

Let 𝐺 be a graph with 𝑛 vertices. What is the maximum number of edges that 𝐺 can have?

In a simple graph with 𝑛 vertices, each pair of distinct vertices can be connected by at most one edge. This means the maximum number of edges occurs when every vertex is connected to every other vertex.

The total number of ways to choose 2 vertices from 𝑛 vertices (i.e., the number of pairs of vertices) is given by the binomial coefficient (combinatorics):

𝐶2𝑛=(𝑛2)=𝑛(𝑛−1)2

Thus, the maximum number of edges in a simple graph with 𝑛 vertices is 𝑛(𝑛−1)2.


Alternatively, we can use the summation formula:

A graph on four vertices with edges grouped as three, two, and one

The pictured graph has 3+2+1 edges. For 𝑛 vertices, the same grouping gives:

(𝑛−1)+⋯+1=∑𝑖=1𝑛−1𝑖=(𝑛−1)((𝑛−1)+1)2=𝑛(𝑛−1)2

Question 12

You are given two sorted lists, each containing 𝑛 numbers. What is the best time complexity to merge these two lists into one sorted list?

Since both lists are already sorted, we can use a two-pointer technique to merge them efficiently. We maintain two pointers, one for each list, and compare the elements at these pointers. We append the smaller element to the merged list and move the corresponding pointer forward. This process continues until we have processed all elements from both lists.

The time complexity of this merging process is 𝑂(𝑛), where the two lists contain 2𝑛 elements in total. Therefore, the best time complexity to merge the two sorted lists into one sorted list is 𝑂(𝑛).

Question 13

What is a random variable? (Hint: A random variable is neither random nor a variable.)

A random variable is a mathematical function that maps outcomes of a random process to numerical values.

Suppose 𝑋 is the random variable representing the number of heads in 10 coin flips. If the outcome is H, T, H, H, T, T, H, T, H, T (where H = heads, T = tails), then 𝑋 maps this outcome to the value 5, since there are 5 heads.

𝑋(H, T, H, H, T, T, H, T, H, T)=5

In general, we can write:

𝑋:Ω→ℝ

where Ω is the set of all possible outcomes (the sample space), and ℝ is the set of real numbers. For example,

𝑋(𝜔)=number of heads in𝜔

or using arrow notation:

𝜔↦𝑋(𝜔)

Question 14

You roll a fair die repeatedly until the result is 3. Let 𝑋 be the number of rolls. What is the expected value of 𝑋?

To find the expected value of 𝑋, we can use the concept of geometric distribution. The random variable 𝑋 follows a geometric distribution with success probability 𝑝=16 (the probability of rolling a 3 on a fair six-sided die).

The expected value (mean) of a geometric random variable is given by:

𝐸(𝑋)=1𝑝

Substituting the value of 𝑝:

𝐸(𝑋)=116=6

Therefore, the expected number of rolls until we get a 3 is 6.



© 2026 James Yap

Personal Website and Knowledge Base