B16 Software Engineering Solutions

Theo Costain

Q1

Your complied program should output Hello, World!. Return 0 tells the system that the program completed without error.

Q 2 - Function encapsulation and side-effects

1. Explain what are function side-effects and why should they be avoided.

Function side effects are changes to the system state that act outside of the function scope. For example reading or writing a global variable, as function flow may be depended on the value of this variable. Other common examples are reading or writing files, or interfacing with computer peripherals.

These side effects should be avoided as they violate the black box functionality that is desirable, making the function harder to accurately document and understand.

Side effects are often unavoidable, i.e. sometimes you need to read from a file, but every effort should be made to minimise them.

2. Explain what is meant by encapsulation in software design and why it is important.

Encapsulation is the process of separating explicitly the interface of a software component from its implementation. The interface defines the ways in which the software component can interact with other components. If the interface is clearly specified, then the component can be re-used with confidence, even if its internal implementation details change. Another benefit of good encapsulation is to make the behaviour of the function explicit, reducing the risk of unexpected side-effects.

In the context of procedural programming, the software components of primary interest are functions/procedures. The operation and interface of a well designed function are transparent from the function header (prototype) which gives the set of inputs (parameters)and outputs (function return values or in the case of C++, perhaps non-constant reference parameters). This encapsulates the function’s meaning, without revealing its internal implementation details. The C and MATLAB standard libraries are good examples of this level of encapsulation. A programmer can use these libraries without needing to know the internal implementation details, and (unless otherwise documented and in limited and well defined cases) can be confident that the operation is neither dependent on, nor affects the values of, global variables.

3. Determine what the code below does, indicate its design flaws, and improve its design and presentation.

// original code
#include <stdio.h>

int num,res; void r(int s) {
while (num>=0) { num = num-s; } num=num+s;  res=num;}int main() {num = 10;
r(4); printf
("%d\n"    , res
) ; }

2

First, lets clean the code up and fix the formatting.

// Cleaned code 
#include <stdio.h>

int num, res;

void r(int s){
    while (num >= 0){
        num = num-s;
    };
    num = num+s;
    res = num;
}

int main() {
    num = 10;
    r(4);
    printf("%d\n", res);
}

2

From here, it's clear that the code is using global variables, which means side effects. Also, the interface to the function is not explicit at all (i.e. bad encapsulation).

Let's fix that by removing the side effect from the function and cleaning up the interface.

// Improved code
#include <stdio.h>

int r(int s, int num){
    while (num >= 0){
        num = num-s;
    }
    num = num + s;
    return num;
}

int main() {
    printf("%d\n",r(4,10));
}

2

Good. Now, have you thought about what are valid values for s? What happens if it's negative? Or what about negative num?

For bonus points, figure out what the code does, and realise that there is a built in operator to do this in C already, that might resolve some of the problems above.

A really important skill in programming is understanding that lots of the time, the thing you want to do has been done before. Especially in popular languages, there is usually a library that will do what you want better than you can do yourself, e.g. NumPy

// improved code (smartass)
#include <stdio.h>

int main(){
    printf("%d\n", 10 % 4);
}

2

Q3 - Parameters, Recursion and the Stack

The Chebyshev polynomials of the first kind T n (x) are defined recursively by $$T_0 (x) = 1$$ $$T_1 (x) = x$$ $$T_{n+1} (x) = 2xT_n (x) − T_{n−1} (x)$$

The following MATLAB code evaluates T n (x) at point x for a given polynomial order n:

function ChebyshevExample()
% plot the Cheybshev polynomial of order n in the interval -10,10
    n = 4;
    t = [-10:0.01:10];
    plot(t,chebyshev(n,t));
    y = chebyshev(3, [-2:1:2]);

% Chebyshev polynomials evaluation
function val = chebyshev(n,x)
    if n == 0
    val = ones(size(x)) ;
    else
    if n == 1
    val = x ;
    else
    val = 2 . * x . * chebyshev(n-1,x) - chebyshev(n-2,x) ;
    end
    end

1. With reference to the code, define and identify the formal and actual parameters of the function chebyshev and the function call.

The formal parameters are n and x and val is the return value. In the first call n = 4 and x = [-10:0.01:10] then in the second call n = 3 and x = [-2,-1,0,1,2]

2. For the second function call, show the evolution of the stack and the final value of the vector returned.

The included figure shows the evolutoin of the stack.

Note how the stack changes in size, both increasing and decreasing as the function recurses.

Q4 - Parameters and Recursion

1. Write a recursive MATLAB function to compute the n^th Fibonacci number, where the first two Fibonacci numbers are 1 and 1, and each subsequent number is the sum of the previous two.

function res = fib_b_rec(n)
    if n == 1 || n == 2
        res = 1;
    else
        res = fib_b_rec(n-1) + fib_b_rec(n-2)
    end
end

2. Write a non-recursive function to do the same.

function result = fib0(n)
    old = 1;
    new = 1;
    for i = 2:n
        tmp = old + new;
        old = new;
        new = tmp;
     end
     result = new;
     return
end

3. If your answer to part (i) involves binary recursion (i.e. the function calls itself twice), consider the cost of this, and devise a recursive algorithm that uses linear recursion instead (i.e. the function call itself only once).

function [res,prev] = fib1(n)
    if n==1
        res = 1;
        prev = 0;
    elseif n==2
        res = 1;
        prev = 1;
    else
        [f1,f2] = fib1(n-1);
        res = f1+f2;
        prev = f1;
    end
end

4. Compare the amount of work required by binary recursion and linear recursion by sketching a trace of the function calls. Is binary recursion doing redundant work?

Below is a chart of the number of function calls made by each algorithm against n. Note the y axis is logarithmic

The important thing to note here comes from the call tree (below) where you can see that the same call is made several times. This is a common problem in programming, for which one solution is memoisation.

_If interested you can have a look at memoisation in python or caching on the web_

Q5 - Sorting, loop invariants and passing functions as parameters

1. Determine the order $O(f (N ))$ of the algorithm.

The order in "big o" notation is given by the highest power in the equation determining runtime. So, for this function we have $$\sum^{N-1}_{i=1}(N-i) = \frac{N(N-1)}{2} = \frac{N^2}{2} - \frac{N}{2}$$ Therefore the complexity of this function is $O(N^2)$