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.

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

	\usepackage{latexsym}
	\usepackage[empty]{fullpage}
	\usepackage{titlesec}
	\usepackage{marvosym}
	\usepackage[usenames,dvipsnames]{xcolor}
	\usepackage{verbatim}
	\usepackage{enumitem}
	\usepackage{amssymb}
	\usepackage[colorlinks,urlcolor=black]{hyperref}
	\usepackage{fancyhdr}

	#include <cassert>
	#include <vector>

	// Given some price information at discrete time intervals, returns a suitable
	// value for the price at a given time interval. You may assume that times is
	// sorted in ascending order, and that there are at least two datapoints (i.e.
	// prices for at least two times).
	auto stock_price(int time, std::vector<int> const &times,
	std::vector<float> const &prices) -> float {
	return 0;

	########################
	# File system commands #
	########################

	# Show the current working directory
	pwd

	# View the contents of the working directory
	ls

	% I'm assuming you have the package imported already
	\usepackage{bussproofs}

	% In these examples, I like indenting the InfC part of each proof tree from the AxiomC(s) that spawned it,
	% and keeping those AxiomC(s) on the same indent level, but I keep the bottom, final InfC unindented
	% This is a personal choice but it makes it easier to keep track of what's happening for large trees

	% A rule with no assumptions (i.e. an axiom)
	\begin{prooftree}
	\AxiomC{}