L2: Divide-and-Conquer

In this lab we consider the problems from Jutge.org, section EDA \rightarrow Divide and Conquer. The problems in this section are of three different types

Efficient exponentiation

A second line of exercises are about efficient exponentiation (in one way or another). They are the following.

The Fibonacci sequence (F_n)_{n\in \mathbb N} is defined as follows: F_0=0, F_1=1 and for every n\geq 2, F_n=F_{n-1}+F_{n-2}. That is \begin{pmatrix} F_n\\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 &1\\ 1& 0 \end{pmatrix} \cdot \begin{pmatrix} F_{n-1}\\ F_{n-2} \end{pmatrix} = \begin{pmatrix} 1 &1\\ 1& 0 \end{pmatrix} ^2 \cdot \begin{pmatrix} F_{n-2}\\ F_{n-3} \end{pmatrix} =\cdots = \begin{pmatrix} 1 &1\\ 1& 0 \end{pmatrix} ^{n-1} \cdot \begin{pmatrix} F_{1}\\ F_{0} \end{pmatrix} \ .

It is not hard to see (by induction on n), that \begin{pmatrix} 1 &1\\ 1& 0 \end{pmatrix} ^{n-1} = \begin{pmatrix} F_n &F_{n-1}\\ F_{n-1}& F_{n-2} \end{pmatrix} for each n\geq 2.

Once you have chosen a problem to solve, download the .zip archive of the problem and unzip it. In the obtained folder there are:

  • a file .pdf with the official problem statement
  • one or more text files with examples of input sample.inp
  • the corresponding correct outputs sample.cor

After creating a C++ source file to solve the problem, compile it with g++ -std=c++11.

Common error(s)

Not using the flag -std=c++11.

Possible useful flags are -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG

Test the executable file obtained on the given example(s), for instance with ./a.out < sample.inp > output. Also, test your code against simple/trivial inputs, e.g. a graph with no-edges.

Common error(s)

Writing the input by hand.
Not checking the exact formatting of the output.

To see whether the output is the same as sample.cor a way is to use diff output sample.cor

Once the code compiles and on the given samples it gives the correct output submit it to the Jutge for automatic evaluation.

Common error(s)

Sending to the Jutge code that was not even compiled locally.
Not checking if the output was correct on the given inputs.

You are “stuck” on a problem if you spent around 1 hour trying to solve it but still the Jutge is rejecting your solution.

Possible approaches to getting “un-stuck” are:

  • do not think about that problem for some time and come back to your code with fresh eyes

  • look again at the theory

  • try to explain your code to another student

  • ask for hints, e.g. by email. Be specific on the type of help you need. Include in the email the code of your approach.


From this block of exercises, in class we solve together the ones marked with 🔶. They are the same as the one listed below.2

Wildcards

A third type of exercises don’t really share much similarities (apart from being amenable to a divide-and-conquer approach). They are the following.

Once you have chosen a problem to solve, download the .zip archive of the problem and unzip it. In the obtained folder there are:

  • a file .pdf with the official problem statement
  • one or more text files with examples of input sample.inp
  • the corresponding correct outputs sample.cor

After creating a C++ source file to solve the problem, compile it with g++ -std=c++11.

Common error(s)

Not using the flag -std=c++11.

Possible useful flags are -Wall -Wextra -Wno-overflow -Wpedantic -Werror -D_GLIBCXX_DEBUG

Test the executable file obtained on the given example(s), for instance with ./a.out < sample.inp > output. Also, test your code against simple/trivial inputs, e.g. a graph with no-edges.

Common error(s)

Writing the input by hand.
Not checking the exact formatting of the output.

To see whether the output is the same as sample.cor a way is to use diff output sample.cor

Once the code compiles and on the given samples it gives the correct output submit it to the Jutge for automatic evaluation.

Common error(s)

Sending to the Jutge code that was not even compiled locally.
Not checking if the output was correct on the given inputs.

You are “stuck” on a problem if you spent around 1 hour trying to solve it but still the Jutge is rejecting your solution.

Possible approaches to getting “un-stuck” are:

  • do not think about that problem for some time and come back to your code with fresh eyes

  • look again at the theory

  • try to explain your code to another student

  • ask for hints, e.g. by email. Be specific on the type of help you need. Include in the email the code of your approach.


From this block of exercises, in class we solve together the ones marked with 🔶. They are the same as the one listed below.3

Fixed points
No matching items

Remember that for any doubt on the exercises you can ask me by email too until 6 days before the lab exam.

Footnotes

  1. Recall that ❗ marks possibly harder problems.↩︎

  2. Recall that ❗ marks possibly harder problems.↩︎

  3. Recall that ❗ marks possibly harder problems.↩︎