The Take Home Assignment of the Application Process

24 November 2018

Shiri Avni

When applying for the computer science MSc at Oxford, the next stage after submitting the personal statement and reference letters is a take-home assignment. I was given 48 hours to complete the assignment - the questions were not difficult, and I believe can be done without much effort by anyone who has completed a computer science bachelor degree.

The questions you receive depend on your academic background. Some of my colleagues, who came from a non-CS fields, were tasked with solving basic questions about code and linear algebra concepts.

While I no longer have my original questions, I can roughly guess what they were from my answers. For the computer science applicants, I hope this helps you narrow down which subjects to review.

1st Question

Tell us about a mathematical course you enjoyed studying during your undergraduate degree and how it is applied in computer science. Write around 250 words.

Answer

Although I love mathematics in general, one field that I have found especially interesting is linear algebra. I first became interested in this field when I discovered that one could determine whether a system of equations has none, one, or infinitely many solutions using an abstract object called a determinant. Although I later learned that a determinant is not used in practice due to its computational complexity, I was still captivated by the idea of approaching a practical problem with a more higher-level perspective.

In the same spirit, the use of eigenvectors and eigenvalues to characterize sets of linear transformations also fascinated me. I was initially exposed to their use in phsyics, my other undergraduate major, in order to help decouple dependent differential equations and find the natural frequencies and energy levels of quantum systems. But I must confess that I was more impressed when I found out about their uses in computer science:

  • To reduce a dataset’s dimensionality, thus saving an enormous amount of storage memory.
  • In Google’s PageRank algorithm

Linear Algebra is ubiquitous in computer science. For instance, it’s useful in computer graphics because many common geometrical transformations, such as rotation and shearing, are linear operations. Linear algebra is also used to gain insights into graph theory. For example, by taking powers of the adjacency matrix of a graph, one can find the length of a walk between two vertices. Linear algebra can be used to find approximate solutions when none exists, which can happen when there are more equations than variables: a classic example is provided by the analytic solution of the Least Squares problem.

2nd Question

A. Given an (,) grid, how many paths are there from to ?

Answer

While you can solve this question for a specific value of using dynamic programming (or recursion, if your computer has the memory capacity), combinatorics allows you to obtain a general solution:

One must take moves down (D) and moves right (R), for a total of steps. If we order the steps and give them labels from to , then we simply need to count the number of ways to select of these labels (without caring about order), and assign them to D (for instance). In short, there are paths.

B. Given different baskets and identical apples, such that , how many ways can we allocate the apples such that no basket is empty?

Answer

This is a “Combinations with Repetitions”1 problem. However, since and we require that no basket be empty, apples are already accounted for: each of the first apples must go into the different baskets, and there is only one way to do this since they are indistinguishable.

The remaining apples can go into any of the baskets, and there are , which gives us the final answer (multiplied by the factor of 1 from earlier).

3rd Question

Given a connected graph with vertices (), where each vertex starts with a color of red or blue, at each time step a vertex becomes the color that is the majority of its neighbors’ colors, and does not switch if there is a tie.

Prove or disprove the following claim: If the graph reaches a static situation, then all vertices are of the same color.</i>

Answer

I spent a while trying to prove this claim, but it is actually false. A counter example is seen below. Half the vertices are red and the other half are blue, but none of the vertices can change colors.

drawing

4th Question

Unfortunately I do not recall the last question precisely, but it was a simple coding question (psuedocode was fine), in which you needed to be able to explain your algorithm, as well as its time and space complexity. Stirling’s approximation came in handy at some point…

Conclusion

If you review your basic courses from your bachelor’s, you should be fine. In my year, combinatorics, algorithms, and general math knowledge were enough, but I would also recommend reviewing probability and computation theory.


Relevant Posts:

A Year at Oxford - Coming with a Family
Oxford Scholarships & WHT
Oxford FAQ