Skip to main content

Section D.6 Exercise Sheet 6

1. Dynamic Programming - Basics.

  1. For which kinds of problems is dynamic programming applicable? What core assumption has to be made in order for dynamic programming to be helpful?

  2. How does the running time of the program change when dynamic programming is used correctly?

  3. How does the memory consumption of the program change when dynamic programming is used correctly?

202207281550

202205201400
Solution.
  1. The problem must consist of overlapping sub-problems.

  2. The runtime of the program is shortened, even drastically depending on the problem.

  3. The memory consumption of the program increases.

2. Dynamic Programming - Sequences.

Konrad Klug wants to calculate the numbers of the integer sequences below. Unfortunately, he cannot write down the sequences in explicit form without recursion. Therefore, he wants to compute the numbers using a C program. He knows that calculating function values multiple times for the same argument is a bad idea, and that he can use dynamic programming to reuse previous calculations. Regretably, he has no time to write his program because of his math classes, so you have to write the program for him.

  1. \(a_n = 3a_{n-3}+a_{n-1}+7\) where \(a_0 = 1, a_1=2, a_2=4\) and the 100th sequence element shall be calculated.

  2. \(b_n = b_{n-1} \cdot b_{n-2}\) where \(b_0 = 1, b_1=2\) and the 8th sequence element shall be calculated.

202207281550

202205201400
Solution.
  1. int sequence_an() {
        int* m = malloc(sizeof(int) * 100);
        m[0] = 1;
        m[1] = 2;
        m[2] = 4;
    
        for (int i = 3; i < 100 ; i++) {
            m[i] = 3 * m[i-3] + m[i-1] + 7;
        }
    
        int res = m[99];
        free(m);
    
        return res;
    }
    

  2. int sequence_bn(){
        int* m = malloc(sizeof(int) * 8);
        m[0] = 1;
        m[1] = 2;
    
        for (int i = 2 ; i < 8 ; i++) {
            m[i] = m[i-1] * m[i-2];
        }
    
        int res = m[7];
        free(m);
    
        return res;
    }
    

3. C0 AST.

Draw the syntax tree for each of the following C0 programs:

  1. Program 1:

    {
        r = 1;
        while (r <= n) {
            r = r * n;
            n = n - 1;
        }
    }
    

  2. Program 2:

    if (b < a) {
        a = 3;
        abort();
    } else {
        b = 3;
    }
    

  3. Program 3:

    {
        b = 3 * (2 + 1);
        c = a != b;
        while (c) 
            c = 1;
    }
    

202207281550

202205201400
Solution.
Program 1:
Program 2:
Program 3:
Figure D.6.1.

4. Abstract Syntax.

Define the abstract syntax of formulas in propositional logic. These consist of the binary operators \(\lor, \land, \Rightarrow, \Leftrightarrow\) and the unary operator \(\neg\text{.}\)

202207281550

202205201400
Solution.
\begin{equation*} \begin{array}{rclll} \amp \amp \text{Abstract Syntax} \amp \text{Concrete Syntax} \amp \text{Description} \\ \hline \mathit{Op} \ni \mathop{o} \amp := \amp \wedge | \vee | \Rightarrow | \Leftrightarrow \amp o \amp \text{Binary Operators} \\ \mathit{LExpr} \ni l \amp := \amp \mathtt{Var}_x \amp x \amp \text{Variable} \\ \mathit{Expr} \ni e \amp := \amp l \amp l \amp \text{L-Value} \\ \amp | \amp \mathtt{Binary}_{\mathop{o}}[e_1, e_2] \amp e_1\mathop{o} e_2 \amp \text{Binary Expr.} \\ \amp | \amp \mathtt{Neg}[e] \amp \neg e \amp \text{Unary Expression} \\ \end{array} \end{equation*}

5. Missing Declarations.

What happens when you execute the following program on the empty state?

x = 1;

202207281550

202205201400
Solution.

Since the container of the variable x does not exist, the program gets stuck (Assign cannot be applied).

6. C0 Syntax.

Find the syntax errors in the following C0 statements.

  1. if (x < y) r = x else r = y;

  2. while a < b {r = r + 1; a = a + 1;}

  3. if (a = 4) b = 42; else b = x;

  4. if (x > y) abort; else r = y;

  5. {x = 5; y = 4;; z = 0;}

  6. if (z < 0) abort() else x = x + y;

  7. r = 42; x = 3; y = x + r;

202207281550

202205201400
Solution.
  1. Semicolon behind the first assignment missing.

    if (x < y) r = x; else r = y;

  2. While condition needs to be parenthesized.

    while (a < b) {r = r + 1; a = a + 1;}

  3. Equality comparison with =, instead of ==.

    if (a == 4) b = 42; else b = x;

  4. Parentheses for abort missing.

    if (x > y) abort(); else r = y;

  5. Too many semicolons.

    {x = 5; y = 4; z = 0;}

  6. Missing semicolon behind abort.

    if (z < 0) abort(); else x = x + y;

  7. Missing Block.

    {r = 42; x = 3; y = x + r;}

7. Expression Evaluation.

Consider the C0 expression evaluation of an expression \(e\text{.}\) What is the difference between the following situations: \(\denotR e\sigma\) is undefined and \(\denotR e\sigma=\indetval\text{.}\)

What happens during execution of the statement x = e; when \(\denotR e\sigma=\indetval\) holds?

202207281550

202205201400
Solution.

If an address is not in the preimage of the memory mapping, then no container for this address exists. The value \(\indetval\) is the undefined value, which is in the container before a value has been assigned to it.

This leads to the uninitialized value \(\indetval\) being read, on which expression evaluation is not defined.

8. Shorthand Notation.

Consider the following state in shorthand notation as defined in the lecture script:

\begin{equation*} \sigma= \{ \texttt{x} \mapsto 1, \texttt{y} \mapsto 2 \} \end{equation*}

Write down \(\rho\) and \(\mu\text{.}\) Use \(\adra, \adrb \dots\) do depict addresses.

202207281550

202205201400
Solution.
\begin{gather*} \sigma = (\rho, \mu) \text{ where}\\ \rho = \{\texttt{x}\mapsto \adra, \texttt{y}\mapsto \adrb\},\\ \mu = \{\adra \mapsto 1, \adrb \mapsto 2\} \end{gather*}

9. Modulo Calculation.

  1. Execute the following program according to C0 semantics on the state

    \begin{equation*} \rho := \{a \mapsto \adra ,b \mapsto \adrb\}, \mu := \{\adra \mapsto 42, \adrb \mapsto 17\} \end{equation*}

    {
        while (a >= b)
            a = a - b;
        if (a == 8)
            abort();
        else
            b = 0;
    }
    

  2. Which kind of program stoppage occurs? How does it look when we instead choose \(\mu := \{\adra \mapsto 40, \adrb \mapsto 17\}\text{?}\) How does the program stop when we choose \(\mu := \{\adra \mapsto 42, \adrb \mapsto 0\}\text{?}\)

    Remark: A short explanation suffices.

202207281550

202205201400
Solution.
  1. To improve readability, we use the shorthand S for the if statement and W for the while statement.

    \(\langle \texttt{\{while(a>=b) a=a-b; S\}} \mid\)
    \(\rho, \{\adra \mapsto 42, \adrb \mapsto 17\} \rangle\)
    \(\rightarrow\) \(\langle \texttt{\{if(a>=b)\{a=a-b; W\} else \{\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 42, \adrb \mapsto 17\}\rangle\)
    [While][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{a=a-b; W\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 42, \adrb \mapsto 17\}\rangle\)
    [IfTrue][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{while(a>=b) a=a-b;\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 25, \adrb \mapsto 17\}\rangle\)
    [Assign][Exec][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{if(a>=b)\{a=a-b; W\} else \{\}\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 25, \adrb \mapsto 17\}\rangle\)
    [While][Subst][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{\{a=a-b; W\}\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 25, \adrb \mapsto 17\}\rangle\)
    [IfTrue][Subst][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{\{while(a>=b) a=a-b;\}\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\)
    [Assign][Exec][Subst][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{\{if(a>=b)\{a=a-b; W\} else \{\}\}\} S\}} \mid\)
    \(\rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\)
    [While][Subst][Subst][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{\{\{\}\}\} S\}} \mid \rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\) [IfFalse][Subst][Subst][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{\{\}\} S\}} \mid \rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\) [Empty][Exec][Subst][Subst]
    \(\rightarrow\) \(\langle \texttt{\{\{\} S\}} \mid \rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\) [Empty][Exec][Subst]
    \(\rightarrow\) \(\langle \texttt{\{if(a==8) abort(); else b=0;\}} \mid\)
    \(\rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\)
    [Empty][Exec]
    \(\rightarrow\) \(\langle \texttt{\{abort();\}} \mid \rho, \{\adra \mapsto 8, \adrb \mapsto 17\}\rangle\) [IfTrue][Subst]
    \(\rightarrow\) \(\Lightning\) [Abort][Crash]
  2. The program aborts. For \(\mu := \{\adra \mapsto 40, \adrb \mapsto 17\}\) the program terminates in state \(\{ \adra \mapsto 6, \adrb \mapsto 0 \}\text{.}\) Except for the value of \(\adra\) the semantics is identical to part a). For \(\mu := \{\adra \mapsto 42, \adrb \mapsto 0\}\) the program diverges (does not stop) since the condition of the while loop is persistently true.

10. Do-While-Loops in C0.

Extend the abstract syntax and the statement semantics of C0 to include the do-while-loop (see control flow section in the C chapter of the script).

202207281550

202205201400
Solution.

Extension of the statement syntax:

\begin{equation*} \textbf{do} \ s\ \textbf{while} (e) \end{equation*}

Extension of the operational semantics:

\begin{equation*} [\text{DoWhile}] \qquad \langle \textbf{do} \ s\ \textbf{while} (e) \mid \sigma \rangle \rightarrow \langle \{s\ \textbf{while} (e) \ s\} \mid \sigma \rangle \end{equation*}

11. For-Loops in C0.

Extend the abstract syntax and the statement semantics of C0 to include a restricted for-loop which shall have the (abstract) syntax:

\begin{equation*} \textbf{for}\ (x\ = \ e_1; \ e_2; \ x\text{++}) \ s \end{equation*}
202207281550

202205201400
Solution.

Extension of the statement syntax:

\begin{equation*} \textbf{for}\ (x\ =\ e_1;\ e_2;\ x\text{++})\ s \end{equation*}

Extension of the operational semantics:

\begin{equation*} [\text{For}] \qquad \langle \textbf{for}\ (x\ =\ e_1;\ e_2;\ x\text{++})\ s \mid \sigma \rangle \rightarrow \langle \{x\ =\ e_1;\ \textbf{while} (e_2)\ \{ s\ \ x = x\ +\ 1;\} \} \mid \sigma \rangle \end{equation*}

Bonus

12. Dynamic Programming - Board Games.

Consider a two-dimensional board, similar to a chess board, with height \(h\) and width \(w\text{.}\) Every position on that board has an integer cost. You start at the top row, in a column chosen by you. In every turn, you must move down one row. While doing so, you can also move one column to the left or to the right (or stay at the same column). The goal of the game is to arrive at the bottom row of the board as cheaply as possible, i.e. so that the sum of the costs of all visited positions is minimal.

Represent the board as an integer array of length \(w \cdot h\) and implement an algorithm with the help of dynamic programming which computes a path of minimal cost, as well as the optimal starting column. Test your program with the following values:

int board[] = {12, 25, 63, 8, 59, 1, 15, 42, 25, 3, 36, 18};
int h = 3;
int w = 4;
Figure D.6.2. The board represented by the array above, with the cheapest path highlighted in yellow.

202207281550

202205201400
Solution.

#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  int parent_col;
  int total_cost;
} Pair;

Pair *shortest_path(const int *board, int h, int w);

/**
 * entry point
 *
 * @return exit
 */
int main() {

  // initialize values
  int board[] = {12, 25, 63, 8, 59, 1, 15, 42, 25, 3, 36, 18};
  int h = 3;
  int w = 4;

  // compute weight table
  Pair *table = shortest_path(board, h, w);

  // allocate memory to store result
  Pair *path = (Pair *)malloc(h * sizeof(Pair));

  // calculate minimum of last row
  int min_dis = INT_MAX;
  int min_col = 0;
  for (int i = 0; i < w; i++) {
    int a = table[(h - 1) * w + i].total_cost;
    if (a < min_dis) {
      min_dis = a;
      min_col = table[(h - 1) * w + i].parent_col;
      path[h - 1].parent_col = i;
      path[h - 1].total_cost = h - 1;
    }
  }

  // add parents with minimal costs to path
  for (int i = h - 2; i >= 0; i--) {
    path[i].parent_col = min_col;
    path[i].total_cost = i;
    min_col = table[i * w + min_col].parent_col;
  }

  // print result to stdout
  printf("shortest path has length %d\n", min_dis);
  for (int i = 0; i < h; i++) {
    printf("%d. (%d, %d)\n", i + 1, path[i].parent_col, path[i].total_cost);
  }

  // free and exit
  free(path);
  free(table);
  return 0;
}

/**
 * calculate shortest path using dynamic programming
 *
 * @param board
 * @param h height
 * @param w width
 * @return weight table
 */
Pair *shortest_path(const int *board, int h, int w) {

  // allocate memory for table
  Pair *table = (Pair *)malloc(h * w * sizeof(Pair));

  // set values of parent_col row
  for (int i = 0; i < w; i++) {
    table[i].total_cost = board[i];
    table[i].parent_col = i;
  }

  // iterate over remaining rows
  for (int i = 1; i < h; i++) {
    for (int j = 0; j < w; j++) {
      int pos = w * i + j;
      table[pos].total_cost = board[pos];

      // left parent
      int a = j - 1 >= 0 ? table[(i - 1) * w + j - 1].total_cost : -1;

      // middle parent
      int b = table[(i - 1) * w + j].total_cost;

      // right parent
      int c = j + 1 < w ? table[(i - 1) * w + j + 1].total_cost : -1;

      // set table entry to minimum of path cost and corresponding column
      if (j - 1 >= 0 && a < b) {
        //if we can go to the left and it is cheaper than the middle
        if (j + 1 >= w || a < c) {
          //if we can not go to the right or it is more expensive than going left
          table[pos].parent_col = j - 1;
          table[pos].total_cost += a;
        } else {
          //we can co to the right and it is cheaper than going left
          table[pos].parent_col = j + 1;
          table[pos].total_cost += c;
        }
      } else {
        if (j + 1 >= w || b < c) {
          table[pos].parent_col = j;
          table[pos].total_cost += b;
        } else {
          table[pos].parent_col = j + 1;
          table[pos].total_cost += c;
        }
      }
    }
  }
  return table;
}

13. Maximal Continuous Sub-Array Sum.

Let \(A\) be an array filled with integers. Consider the problem of finding a continuous sub-array with maximal sum. For example, consider the array

\begin{equation*} A = [-5,3,4,-2,6,-5,-8,4,3]. \end{equation*}

The continuous sub-array with maximal sum of \(A\) is the sub-array \([3,4,-2,6]\) with a sum of \(3+4+(-2)+6 = 11\text{.}\)

  1. First, we want to compute the maximal sum for a restricted case. Define a recursive mathematical function \(\operatorname{mT}(i)\) specified as follows: For all \(0 \leq i < n\text{,}\) \(\operatorname{mT}(i)\) considers all sub-arrays

    \begin{equation*} A' = [A[j], A[j+1], \dots, A[i]] \end{equation*}
    which start at any index \(j \in \{ 0, \dots, i\}\) and end at index \(i\) (both inclusive), and gives the maximal sum, i.e. the sum of the sub-array with the largest sum. For example, for \(i=3\) and the array \([-5,3,4,-2,6,-5,-8,4,3]\) we have \(\operatorname{mT}(i) = 3+4+(-2) = 5\text{,}\) sine the sub-array starting at \(j=1\) has the largest sum.

  2. Apply the function on the array \([-5,3,4,-2,6,-5,-8,4,3]\) for every end index \(i\) of the sub-array. Draw a corresponding table with your calculations for every end index \(i\text{.}\) What do you notice?

  3. Write a C program which uses the function from part a) to calculate the sum of the continuous sub-array with maximal sum.

  4. Extend the program such that the maximal sub-array is calculated and printed.

202207281550

202205201400
Solution.
  1. \begin{equation*} \operatorname{mT}(i) = \begin{cases} A[i] & i = 0\\ A[i] + \max \{\operatorname{mT}(i - 1),0\} & i > 0 \end{cases} \end{equation*}
  2. \(A = [-5,3,4,-2,6,-5,-8,4,3], n = 9\)

    \(i\) \(A[i]\) \(\operatorname{mT}(i)\)
    \(0\) \(-5\) \(-5\)
    \(1\) \(3\) \(3 + \max \{ \operatorname{mT}(0), 0 \} = 3\)
    \(2\) \(4\) \(4 + \max \{ \operatorname{mT}(1), 0 \} = 7\)
    \(3\) \(-2\) \(-2 + \max \{ \operatorname{mT}(2), 0 \} = 5\)
    \(4\) \(6\) \(6 + \max \{ \operatorname{mT}(3), 0 \} = 11\)
    \(5\) \(-5\) \(-5 + \max \{ \operatorname{mT}(4), 0 \} = 6\)
    \(6\) \(-8\) \(-8 + \max \{ \operatorname{mT}(5), 0 \} = -2\)
    \(7\) \(4\) \(4 + \max \{ \operatorname{mT}(6), 0 \} = 4\)
    \(8\) \(3\) \(3 + \max \{ \operatorname{mT}(7), 0 \} = 7\)

    One can directly read the maximal continuous sub-array sum from the table. It is the maximum of all the values in the rightmost column. Additionally, one can get the corresponding sub-array by choosing the index \(j\) corresponding to the maximum value as the last element index of the sub-array. For the starting index, one descends from the last index and chooses the smallest index \(i\) for which the value in the rightmost value is positive. In the example, these indices are \(j := 4\) and \(i := 1\text{.}\) The corresponding sub-array is \([3,4,-2,6]\) with sum \(11\text{,}\) which is the desired result.

  3. #include <stdio.h>
    
    int max_sum(int *array, int length) {
        if (length < 1)
            return 0;
    
        int* sums = malloc(sizeof(int) * length);
        sums[0] = array[0];
        for (int i = 1; i < length; i++) {
            sums[i] = (sums[i-1] > 0) ? sums[i-1] + array[i] : array[i];
        }
    
        int max = sums[0];
        for (int i = 1; i < length; i++) {
            if (sums[i] > max)
                max = sums[i];
        }
    
        free(sums);
    
        return max;
    }
    
    // or without additional array
    int max_sum_short(int *array, int length) {
        if (length < 1)
            return 0;
    
        int last_sum = array[0];
        int max = last_sum;
    
        for (int i = 1; i < length; i++) {
            last_sum = (last_sum > 0) ? last_sum + array[i] : array[i];
            if (last_sum > max)
                max = last_sum;
        }
    
        return max;
    }
    
    int main(int argc, char **argv) {
        int array[] = {-5,3,4,-2,6,-5,-8,4,3};
        int res = max_sum(array, sizeof(array)/sizeof(int));
    
        printf("The maximal continuous sub-array sum is %d\n", res);
    
        return 0;
    }
    

  4. #include <stdio.h>
    
    typedef struct {
        int max;
        int start;    // inclusive
        int end;    // exclusive
    } subarray_t;
    
    void max_sum_short(int *array, int length, subarray_t *result) {
        if (length < 1) {
            result->max = 0;
            result->start = 0;
            result->end = 0;
            return;
        }
    
        int last_sum = array[0];
        int max = last_sum;
        int start = 0;
        int best_start = 0;
        int end = 0;
    
        for (int i = 1; i < length; i++) {
            if (last_sum <= 0) {
                start = i;
                last_sum = array[i];
            } else
                last_sum += array[i];
            if (last_sum > max) {
                max = last_sum;
                best_start = start;
                end = i+1;
            }
        }
        
        result->max = max;
        result->start = best_start;
        result->end = end;
    }
    
    int main(int argc, char **argv) {
        int array[] = {-5,3,4,-2,6,-5,-8,4,3};
        subarray_t result;
        max_sum_short(array, sizeof(array)/sizeof(int), &result);
    
        if (result.end - result.start >= 1) {
            printf("The continuous sub-array with maximal sum is: [%d", array[result.start]);
            for (int i = result.start+1; i < result.end; i++)
                printf(", %d", array[i]);
            printf("]\n");
            printf("The sum of the sub-array is %d\n",
                    result.max);
        } else
            printf("[]\nThe passed array is empty!");
    
        return 0;
    }