 Home

Codex Wiki

List of universities

University of Oxford

Course of the University of Oxford

Undergraduate course of the University of Oxford

Computer science course of the University of Oxford

Year 1 of the computer science course of the University of Oxford

Past exam of the year 1 of the computer science course of the University of Oxford

2023

Functional programming, design and analysis of algorithms

The three answers, in source order, are:
* \b[$T(n)=\Theta(n^2)$.] In the <Master theorem>, $a=6$, $b=3$, and $n^2$ grows polynomially faster than $n^{\log_3 6}$. The regularity condition holds because $6(n/3)^2=(2/3)n^2$. For powers of three, expansion even gives $T(n)=3n^2-2n^{\log_3 6}$.
* \b[$T(n)=n^2$, and hence $\Theta(n^2)$.] The <telescoping sum> is $T(n)=1+\sum_{j=2}^n(2j-1)=\sum_{j=1}^n(2j-1)=n^2$.
* \b[$T(n)=\Theta(n^{\log_2 3})$.] Set $m=n-2$ and $U(m)=T(m+2)$. Then $U(m)=3U(m/2)+m+2$, with constant base cost for $m\leq2$. The <Master theorem> with $a=3$, $b=2$ applies because $m+2=\Theta(m)$ is polynomially smaller than $m^{\log_2 3}$. Finally $m=n-2=\Theta(n)$.

The change of variable in the third case handles the additive shift in the recursive argument exactly; it is not an unjustified deletion of the `+1`. These <Big theta notation> conclusions use the usual admissible input sizes, or bounded integer rounding of subproblem sizes.

Solution

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 8 / a / Solution

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 8 / a / Solution

 Ancestors (12)

 Discussion (0)

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Functional programming, design and analysis of algorithms / 8 / a / Solution

 Ancestors (12)

 Discussion (0)  Subscribe (1)

 Articles by others on the same topic (0)

 Discussion (0)