Skip to main content

Section D.15 Exam Prep Sheet

This sheet was created by the tutors. The exercises are neither relevant nor irrelevant for the exam. This collection of exercises does not necessarily cover all the materials subject to the exam. You should still revice all material from the lecture notes, exercise sheets, and lecture on your own.

1. Multiple Choice.

For each of the following statements decide if they are true or false. If you think that a statement is false try to explain to yourself why it is false.

  1. The Mips calling convention specifies that the stack pointer and the s-registers need to be restored by the called function before jumping back.

  2. To load a word its address needs to be divisible by 4.

  3. int foo(int x); is a valid function declaration in C.

  4. Every expression can be R-evaluated.

  5. In C it always holds that sizeof(char) smaller or equal sizeof(long).

  6. Dividing by zero is undefined behaviour in Java.

  7. boolean and int can be implicitly converted to each other in Java.

  8. A method without visibility modifiers can be called by methods within the same package.

  9. The load factor of a hash table can be computed by dividing the number of inserted elements by the size of the hash table.

  10. To run through every position in a hash table using quadratic probing it is not important to use a surjective hash function.

  11. Linear probing aims to prevent the formation of clusters.

  12. Black Box tests try to achieve full branch, path and code coverage.

  13. In a Hoare triple we can strengthen preconditions.

  14. An assertion A is called stronger than an assertion B if \(B \Rightarrow A\text{.}\)

202210071346

202207221400
Solution.
  1. True.

  2. True.

  3. True.

  4. True.

  5. True.

  6. False, an exception is thrown.

  7. False.

  8. True.

  9. True.

  10. False, if the function isn't surjective it is not possible to go through every position.

  11. False, clusters form using linear probing, quadratic probing aims to prevent them.

  12. False, Black box testing tests if a program satisfies a specification.

  13. True.

  14. False, A is stronger than B if \(A \Rightarrow B\text{.}\)

2. Insertion Sort in MIPS.

Look at the following code implementing insertion sort.

  1. Fill in the gaps such that swap swaps two elements in an array. The addresses of the elements to be swapped are passed via the registers $a0 and $a1.
    .text
    swap:
      # $a0, $a1 adresses of the elements to be swapped
      lw ____ ____
      lw ____ ____
      sw ____ ____
      sw ____ ____
      jr $ra
    
  2. Now fill in the gaps sucht that insertion_sort follows the calling convention.
    insertion_sort:
      # $a0 base adress of the array
      # $a1 last adress of the array
      beq $a0 $a1 end
      move $t0 $a0
      
      loop:
        addiu $t0 $t0 4
        bgt $t0 $a1 end
        lw $t5 ($t0)
        move $t1 $t0
        
      loop_2:
        beq $t1 $a0 loop
        
        addiu $t2 $t1 -4
        lw $t6 ($t2)
        ble $t6 $t5 loop
        
        addiu $sp $sp -32
        sw ____ ____
        sw ____ ____
        sw ____ ____
        sw ____ ____
        sw ____ ____
        sw ____ ____
        sw ____ ____
        sw ____ ____
        
        move $a0 $t1
        move $a1 $t2
        
        jal swap
        
        lw ____ ____ 
        lw ____ ____ 
        lw ____ ____ 
        lw ____ ____ 
        lw ____ ____ 
        lw ____ ____ 
        lw ____ ____ 
        lw ____ ____ 
        addiu $sp $sp 32
        
        addiu $t1 $t1 -4
        b loop_2
        
      end:
        jr $ra
    
202210071346

202207221400
Solution.

# a)
.text
swap:
  # $a0, $a1 adresses of elements to be swapped
  lw $t0 ($a0)
  lw $t1 ($a1)
  sw $t0 ($a1)
  sw $t1 ($a0)
  jr $ra

# b)  
insertion_sort:
  # $a0 base adress of the array
  # $a1 last adress of the array
  beq $a0 $a1 end
  move $t0 $a0
  
  loop:
    addiu $t0 $t0 4
    bgt $t0 $a1 end
    lw $t5 ($t0)
    move $t1 $t0
    
  loop_2:
    beq $t1 $a0 loop
    
    addiu $t2 $t1 -4
    lw $t6 ($t2)
    ble $t6 $t5 loop
    
    addiu $sp $sp -32
    sw $a0 0($sp)
    sw $a1 4($sp)
    sw $t0 8($sp)
    sw $t1 12($sp)
    sw $t2 16($sp)
    sw $t5 20($sp)
    sw $t6 24($sp)
    sw $ra 28($sp)
    
    move $a0 $t1
    move $a1 $t2
    
    jal swap
    
    lw $a0 0($sp)
    lw $a1 4($sp)
    lw $t0 8($sp)
    lw $t1 12($sp)
    lw $t2 16($sp)
    lw $t5 20($sp)
    lw $t6 24($sp)
    lw $ra 28($sp)
    addiu $sp $sp 32
    
    addiu $t1 $t1 -4
    b loop_2
    
  end:
    jr $ra

3. Pointergolf.

Which output does the following program print? Try to figure out the solution without using a computer. You may find it helpful to write down an execution log, but you are not obligated to do so.

#include <stdio.h>

int main() {

    int a = 3;
    int b = 7;
    int c = 5;

    int m[5] = {1, 2, 3, 4, 5};

    int* pa = &a;
    int* pb = &b;
    int* pc = &c;

    int** ppa = &pa;


    a = *pb;
    pc = &m[3];
    *pc = *pb + 3;
    pb = pc - 1;
    *pb = **ppa;
    *(pc + 1) = c + *pa;
    m[0] = *(pb - 1) + 3;


    printf("a = %d\n", a);
    printf("b = %d\n", b);
    printf("c = %d\n", c);

    printf("m[0] = %d\n", m[0]);
    printf("m[1] = %d\n", m[1]);
    printf("m[2] = %d\n", m[2]);
    printf("m[3] = %d\n", m[3]);
    printf("m[4] = %d\n", m[4]);

    return 1;
}

Write down your solution here:

a =

b =

c =

m[0] =

m[1] =

m[2] =

m[3] =

m[4] =

202210071346

202207221400
Solution.

Output of the program:

a = 7

b = 7

c = 5

m[0] = 5

m[1] = 2

m[2] = 7

m[3] = 10

m[4] = 12

4. Test Suite.

The following C-program calculates the n-th tetranacci number. The tetranacci numbers are a generalization of the Fibonacci numbers.

int tetranacci(int n) {
    if (n < 4) {
        if (n < 3) {
            if (n == 2) {
                return 1;
            } else {
                if (n == 1) {
                    return 1;
                } else {
                    return 0;
                }
            }
        } else {
            return 2;
        }
    } else {
        return tetranacci(n - 4) + tetranacci(n - 3) 
            + tetranacci(n - 2) + tetranacci(n - 1);
    }
}

  1. Write a test suite for the program which covers all statements.

  2. Extend your test suite such that it covers all branches, if possible.

202210071346

202207221400
Solution.
  1. void test_n_zero() {
        int tetranacci = tetranacci(0);
        assert(tetranacci == 0);
    }
    
    void test_n_one() {
        int tetranacci = tetranacci(1);
        assert(tetranacci == 1);
    }
    
    void test_n_two() {
        int tetranacci = tetranacci(2);
        assert(tetranacci == 1);
    }
    
    void test_n_three() {
        int tetranacci = tetranacci(3);
        assert(tetranacci == 2);
    }
    
    void test_tetranacciursion() {
        int tetranacci = tetranacci(4);
        assert(tetranacci == 4);
    }
    

  2. Here, we cannot cover all statements without also covering all branches. We are therefore already done.

5. C0p(b).

  1. Draw the abstract syntax tree of the C0p program

    {
      x = 1;
      y = &x;
      if (*y>0)
        abort();
      else
        x = x + 41;
    }
    
  2. Execute the following C0pb program on the state \(\sigma = (\{\}; \{\})\text{.}\)

    {
      int x;
      int *y;
      int **z;
      x = 42;
      y = &x;
      z = &y;
      if (*y>0)
        **z = *y - *(&x);
      else
        abort();
    }
    
    Explicitly state the evaluation of the expressions \(\texttt{**z}\) and \(\texttt{*y - *(\&x)}\text{.}\)

202210071346

202207221400
Solution.
  1. Abstract Syntax Tree:

    Figure D.15.1.
  2. To improve readability, we use the shorthand S to denote the if statement.

    Execution:

    Figure D.15.2.

    Let

    \begin{equation*} \sigma' := \rho_1 ,\rho_2' ;\mu' := \{ \},\{\texttt x \mapsto \adra, \texttt y \mapsto \adrb, \texttt z \mapsto \adrc\};\{\adra \mapsto 42, \adrb \mapsto \adra, \adrc \mapsto \adrb\}.\\ \end{equation*}
    \begin{align*} \denotL{\texttt{**z}} \sigma' \amp= \denotR{\texttt{*z}} \sigma'\\ \amp= \mu'(\denotL{\texttt{*z}}\sigma')\\ \amp= \mu'(\denotR{\texttt{z}}\sigma')\\ \amp= \mu'(\mu'(\denotL{\texttt{z}}\sigma'))\\ \amp= \mu'(\mu'(\rho_2' \texttt{z}))\\ \amp= \mu'(\mu'(\adrc))\\ \amp= \mu'(\adrb)\\ \amp= \adra \end{align*}
    \begin{align*} \denotR{\texttt{*y-*(\&x)}} \sigma' \amp= \denotR{\texttt{*y}} \sigma' - \denotR{*(\& x)}\\ \amp= \mu'(\denotL{\texttt{*y}} \sigma') - \mu'(\denotL{*(\& x)}\sigma')\\ \amp= \mu'(\denotR{\texttt{y}} \sigma') - \mu'(\denotR{\& x}\sigma')\\ \amp= \mu'(\mu'(\denotL{\texttt{y}} \sigma')) - \mu'(\denotL{x}\sigma')\\ \amp= \mu'(\mu'(\rho_2' y)) - \mu'(\rho_2' x)\\ \amp= \mu'(\mu'(\adrb)) - \mu'(\adra)\\ \amp= \mu'(\adra) - 42\\ \amp= 0 \end{align*}

6. Cars.

Fridolin would really like to buy his first car. Because this is a big expense he wants to compare several cars beforehand. Please help him by first implementing a class Car.

  1. Add a reasonable constructor. Each car has an associated number plate, the remaining distance in kilometers and a price (in euros).

  2. Implement getters for these fields.

  3. Add a method drive(int kilometers) which takes the number of kilometers driven. Update the remaining distance accordingly. If the car cannot drive that far, throw a generic exception.

  4. Now create a second class ElectricCar extending Car. In addition to the properties from Car it has an associated maximum distance it can drive, which the constructor should take into consideration. Electric cars get delivered fully charged. Create a getter for the new property.

  5. Implement a method charge() which fully charges the electric car (sets remaining distance to maximum distance).

  6. Make sure all methods in both classes are publically accessible.

202210071346

202207221400
Solution.

public class Car {
  int remainingDistance;
  String numberPlate;
  int price;

  public Car(int remainingDistance, String numberPlate, int price) {
    this.remainingDistance = remainingDistance;
    this.numberPlate = numberPlate;
    this.price = price;
  }

  public int getRemainingDistance() {
    return this.remainingDistance;
  }

  public String getNumberPlate() {
    return this.numberPlate;
  }

  public int getPrice() {
    return this.price;
  }

  public void drive(int kilometers) throws Exception {
    if (this.remainingDistance < kilometers)
      throw new Exception();
    this.remainingDistance -= kilometers;
  }
}
public class ElectricCar extends Car {
  int maxDistance;

  public ElectricCar(int maxDistance, String numberPlate, int price) {
    super(maxDistance, numberPlate, price);
    this.maxDistance = maxDistance;
  }

  public void charge() {
    this.remainingDistance = maxDistance;
  }

}

7. Inheritance Hierarchy.

Which method is called in each case? State the output of the program.

public class A {
  public void fun(B b) {
    System.out.println("A.fun(B)");
  }
  public void fun(D d) {
    System.out.println("A.fun(D)");
  }
}
public class B extends A {
  public void fun(A a) {
    System.out.println("B.fun(A)");
  }
  public void fun(C c) {
    System.out.println("B.fun(C)");
  }
  public void fun(E e) {
    System.out.println("B.fun(E)");
  }
}
public class C extends B {
  public void fun(B b) {
    System.out.println("C.fun(B)");
  }
}
public class D extends B {
}
public class E extends D {
  public void fun(B b) {
    System.out.println("E.fun(B)");
  }
  public void fun(C c) {
    System.out.println("E.fun(C)");
  }
}
public class F extends A {
  public void fun(A a) {
    System.out.println("F.fun(A)");
  }
  public void fun(D d) {
    System.out.println("F.fun(D)");
  }
}
public class G extends F {
}
public class Main {
    public static void main(
        String[] args) {
        A aa = new A();
        A ab = new B();
        A ac = new C();
        A ag = new G();
        A af = new F();
        B bb = new B();
        B bc = new C();
        B bd = new D();
        B be = new E();
        C cc = new C();
        D dd = new D();
        D de = new E();
        E ee = new E();
        F ff = new F();
        F fg = new G();
        G gg = new G();

        aa.fun(bd);
        ac.fun(bb);
        ac.fun(be);
        af.fun(dd);
        af.fun(ab);
        ag.fun(cc);

        bb.fun(ab);
        bb.fun(bc);
        bc.fun(bb);
        bc.fun(ff);
        bc.fun(dd);
        bd.fun(cc);
        be.fun(bc);
        be.fun(cc);
        be.fun(dd);

        cc.fun(de);
        cc.fun(ee);

        dd.fun(dd);
        dd.fun(bd);
        dd.fun(fg);

        ee.fun(ee);
        ee.fun(cc);

        ff.fun(fg);
        gg.fun(de);
        gg.fun(bc);
    }
}

202210071346

202207221400
Solution.

aa.fun(dd); \(\implies\)A.fun(B)
ac.fun(bb); \(\implies\)C.fun(B)
af.fun(be); \(\implies\)C.fun(B)
af.fun(dd); \(\implies\)F.fun(D)
af.fun(ab); \(\implies\)ERROR!
ag.fun(cc); \(\implies\)A.fun(B)
bb.fun(ab); \(\implies\)B.fun(A)
bb.fun(bc); \(\implies\)A.fun(B)
bc.fun(bb); \(\implies\)C.fun(B)
bc.fun(ff); \(\implies\)B.fun(A)
bc.fun(dd); \(\implies\)A.fun(D)
bc.fun(cc); \(\implies\)B.fun(C)
be.fun(bc); \(\implies\)E.fun(B)
be.fun(cc); \(\implies\)E.fun(C)
be.fun(dd); \(\implies\)A.fun(D)
cc.fun(de); \(\implies\)A.fun(D)
cc.fun(ee); \(\implies\)B.fun(E)
dd.fun(dd); \(\implies\)A.fun(D)
dd.fun(bd); \(\implies\)A.fun(B)
dd.fun(fg); \(\implies\)B.fun(A)
ee.fun(ee); \(\implies\)B.fun(E)
ee.fun(cc); \(\implies\)E.fun(C)
ff.fun(fg); \(\implies\)F.fun(A)
gg.fun(de); \(\implies\)F.fun(D)
gg.fun(bc); \(\implies\)A.fun(B)

8. Hashing Pets.

Your best friend Konrad Klug would like to build up his own pet shop 'Prog Pets'. To keep track which pets can be sold, he would like to have a list in his online shop where there are stored in. Because Konrad tried to safe some money, the computing power of his web server is not very high and therefore searching in big data structures takes much time. No Hau heard of his problem and suggested to use hash tables. Konrad has prepared the following classes.

public class Snake {
    private short length;          // length in cm (max. 900cm)
    private short weight;          // weigth in kg (max. 300kg)
    private boolean isPoisonous;

    // ...
}

public class Fish {
    private String name;
    private int shedNumber;

    @Override
    public boolean equals(Object o) {
        return shedNumber == o.shedNumber;
    }

    @Override
    public int hashCode() {
        return shedNumber / 100;
    }

    // ...
}

  1. Implement the hashCode and equals methods for the class Snake.

  2. Konrad implemented the hashCode and equals methods for the class Fish himself but he made a mistake. Specify the mistake he made and correct the methods.

  3. Hash the following fishes represented by instances of Fish with the corrected methods into a hash table of size 5. Use collision lists to resolve collisions.

    Name Number of Sheds
    Sally 1376
    Bobby 4653
    James 2775
    Ami 3910
    Phil 1597
    Sophie 3841
    Fred 987
    Pepper 987

202210071346

202207221400
Solution.
  1. @Override
    public boolean equals(Object o) {
        if (!(o instanceOf Snake))
            return false;
    
        Snake s = (Snake) o;
        return this.length == s.length && this.weight == s.weight && this.isPoisonous == s.isPoisonous;
    }
    
    @Override
    public int hashCode() {
        return (this.isPoisonous ? 1 : 0) * 53 + this.weight * 37 + this.length * 13;
    }
    

  2. Konrad forgot to check if the given parameter o is of type Fish. The hashCode method is maybe not that well-chosen but it is sufficient for this exercise. Also the name attribute could have been taken into account.

    public class Fish {
        private String name;
        private int shedNumber;
    
        @Override
        public boolean equals(Object o) {
            if (!(o instanceOf Fish))
                return false;
            
            return shedNumber == ((Fish) o).shedNumber;
        }
    
        @Override
        public int hashCode() {
            return shedNumber / 100;
        }
    
        // ...
    }
    

  3. Name Number of Sheds Hash Code Index
    Sally 1376 13 3
    Bobby 4653 46 1
    James 2775 27 2
    Ami 3910 39 4
    Phil 1597 15 0
    Sophie 3841 38 3
    Fred 987 9 4
    Pepper 987 9 4

9. Compiler Impersonation.

Consider the following type environment: \(\Gamma := \{ \CVar{i} \mapsto \CInt, \CVar{it} \mapsto \CPtr\CChar, \CVar{len} \mapsto \CInt \}\)

  1. Check whether the following C0t program has any type errors with respect to the type environment given above:

    while (i < len) {
      void* vp;
      vp = it + i;
    }
    

  2. Generate MIPS code for the subexpression vp = it + i;. Evaluate the lefthand side of binary operators first. Assume the offsets \(\{\CVar{i} \mapsto 0, \CVar{it} \mapsto 4, \CVar{len} \mapsto 8, \CVar{vp} \mapsto 12\}\text{.}\)

202210071346

202207221400
Solution.
  1. The program is well-typed.

    1. \(\mbox{}\)

    2. \(\mbox{}\)

  2. The following listings contain the code used in the derivation trees.

    addiu $t1 $sp 4
    
    Listing D.15.3. Code \(c_1\)
    addiu $t1 $sp 4
    lw $t1 ($t1)
    
    Listing D.15.4. Code \(c_2\)
    addiu $t2 $sp 0
    
    Listing D.15.5. Code \(c_3\)
    addiu $t2 $sp 0
    lw $t2 ($t2)
    
    Listing D.15.6. Code \(c_4\)
    addiu $t1 $sp 4
    lw $t1 ($t1)
    addiu $t2 $sp 0
    lw $t2 ($t2)
    addu $t1 $t1 $t2
    
    Listing D.15.7. Code \(c_5\)
    addiu $t0 $sp 12
    
    Listing D.15.8. Code \(c_6\)
    addiu $t0 $sp 12
    addiu $t1 $sp 4
    lw $t1 ($t1)
    addiu $t2 $sp 0
    lw $t2 ($t2)
    addu $t1 $t1 $t2
    sw $t1 ($t0)
    
    Listing D.15.9. Code \(c_7\)
    1. \(\mbox{}\)

    2. \(\mbox{}\)

    3. \(\mbox{}\)

10. Find the invariant.

Take a look at the following loop, find an invariant and prove that your invariant is valid using Hoare logic derivation rules.

  1. sum = 0;
    i = 1;
    while (i <= n) {
        sum = sum + i;
        i = i + 1;
    }
    
202210071346

202207221400
Solution.

The loop computes the sum of all natural numbers leading up to n. Therefore an invariant we can try is \(\texttt{I := sum = (i-1)(i) / 2}.\)

  1. \(\texttt{With: P':= I; P := sum + i = i * (i + 1) / 2; Q' = Q = I}\)