Advanced Algorithms Quiz 1: 7 July 2024 (May 2024 term)

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the answer if the input is 1 1 2 1?

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the answer if the input is 1 2 3 4 5 6 7 8 9 10?

There are $2n$ positive integers written on a whiteboard. Here is a one-player game with these numbers: You start with a score of 0 . You will increase your score by performing the following move exactly $n$ times:

• Choose two integers $x$ and $y$ that are written on the whiteboard.
• Add $\min(x, y)$ to your score.
• Erase $x$ and $y$ from the whiteboard.

Note that after performing the move $n$ times, there will be no more integers written on the whiteboard. In general, our goal is to find the maximum final score you can achieve if you optimally perform the $n$ moves.

We will refer to this value as the answer.

Based on the above data answer the given subquestions.

What is the answer if 2n = 50 and the input is the set of all even numbers between 1 and 100? (Hint: you might want to use the fact that the sum of the first n odd numbers is n².)