James Davidson jedavidson

Here's the problem.

A more useful way to phrase it is that there are $n$ rounds, with all bulbs initially switched off before round 1, and on round $r$, bulb $k$ is toggled if $r$ divides $k$. Under this formulation, the number of times bulb $k$ is toggled is exactly the number of factors it has, and for an off bulb to be switched on after $n$ rounds, it has to have been toggled an odd number of times. Thus, we need to identify which numbers in $\{1, 2, \ldots, n\}$ have an odd number of factors.

By the fundamental theorem of arithmetic, any integer $k$ factorises into some product of primes, i.e. $$k = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_{m}}$$ for some primes $p_i$ is prime and exponents $e_i > 0$. Each factor of $k$ is thus of the form $$p_1^{e_1'} p_2^{e_2'} \cdots p_m^{e_m'},$$ where $0 \leq e_i' \leq e_i$. Since there are $e_i + 1$ choices for each of these factor exponents $e_i'$, and ea

This is the problem in question.

Let $\ell_i$ be the length of the $i^{\textsf{th}}$ stick. Without loss of generality, we will assume that $$\ell_1 \leq \ell_2 \leq \cdots \leq \ell_n.$$ (The eventual solution has no need for the lengths to be sorted, so this is just for convenience in the correctness proof.)

Making all sticks have length $\ell$ has associated cost $$c(\ell) = \sum_{i = 1}^{n} |\ell_i - \ell|,$$ and the problem asks us for the minimal cost over all lengths. We may as well ask instead for any optimal length $\ell^*$, since we can just compute $c(\ell^*)$ to get the minimal cost if need be.

Consider the following recursive algorithm:

def f(n: int) -> int:
    if n <= 1:
        return 1
    else:
        return g(n) + f(n / 2) + f(n / 2)

Given that g(n) has time complexity $O(\log{n})$, we want to determine the time complexity of f(n). Let's see if we can work out the answer without using any powerful machinery one might initially be tempted to use.[^1] Most of the difficulty will actually be in evaluating sums, but this should be doable if you've done MATH1081.

How to run this:

• Put lru.hpp in the include folder of a project (e.g. the sample exam)
• Put lru_client.cpp in the source folder of a project (e.g. the sample exam)
• Edit the source/CMakeLists.txt file to include

cxx_executable(
    TARGET "lru_client"
    FILENAME "lru_client.cpp"
)

• Attempt eval first, and then try satisfiable.
• Download eval.c and satisfiable.c to your machine by copy/pasting the code into files with the same name.
• Compile using dcc -o eval eval.c and dcc -o satisfiable satisfiable.c respectively.
• Instructions, including the problem statement and how to run each program, are given in each file.
• Good luck!

These exercises are some I did while studying for COMP2521, as well as some others which I've found afterwards which I think will be relevant. I've collected these problems mostly from LeetCode and HackerRank, which are excellent sites for practicing your coding abilities. Accounts on both sites will be necessary to do the problems listed.

The difficulty ranking is obviously my opinion, but generally speaking here is what they mean:

• Easy: Problems that you should be able to do without too much difficulty.
• Intermediate: Problems that are a bit harder, but should be doable with a little bit of thought and intuition.
• Challenges: Problems that I think are difficult and/or interesting, if you're up for it. There are almost all harder than what's within the scope of 2521.

If you're able to solve the easy and intermediate problems without much difficulty, you're probably very well prepared for any programming questions you'll receive in the ex