Structured Programming MT2011                                                     Page/1
                        B16 Structured Programming
     ian.reid@eng.ox.ac.uk                                                 Michaelmas 2011
     www.robots.ox.ac.uk/∼ian/Teaching/B16/                                     Rev 18/1/11
        • For updates, answers and hints, keep in touch with the web page.
        • Email if you are puzzled about a question’s meaning. The reply, if generally
          useful, will be placed in the hints section.
        • In a number of the questions you are asked to write code. Your code need not
          be absolutely syntactically correct (though it would be good if it is), but must
          convey that you have understood the key ideas. If you are not sure about syntax
          then add comments so that someone reading your “pseudo-code” can work out
          your intention.
        • Questions marked [**] are those that might be consdered typical exam type
          questions, though again note that syntactically correct code would not be re-
          quired in an exam.
       1. Software lifecyle: Write notes contrasting the waterfall model of the software
          development lifecycle with extreme programming.
       2. Function encapsulation and side-effects:
          (a) What are function side-effects and why should they be avoided?
          (b) Encapsulationisanimportantconceptinbothproceduralandobject-oriented
              programming. Explain what is meant by encapsulation, and why it is im-
              portant in software design and implementation.
          (c) Consider the mess in the code box below. Determine what the code does,
              indicate design flaws, and hence tidy it into something sensible.
               #include ¡iostream¿
               int num,res; void r(int s) –
               while (num¿0) – num = num-s; ˝ num=num+s;  res=num;˝ int main() – num = 10;
               r(4); std::cout ¡¡ res ¡¡ std::endl; ˝
       3. Parameters, recursion and the stack: [**]
          (a) With reference to the code, define and identify the formal and actual pa-
              rameters of the function chebyshev and the function call.
          (b) For the second function call, show the evolution of the stack and the final
              value of the vector returned.
   Structured Programming MT2011              Page/2
        %%% script
        a = 4;
        t = [-10:0.01:10];
        plot(t,chebyshev(a,t));
        y = chebyshev(3, [-2:1:2]);
        %%%% function chebyshev
        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
    4. Parameters and recursion: [**]
      (a) Write a recursive matlab function to compute the the nth Fibonacci number,
        where the first two Fibonacci numbers are defined to be 1 and 1, and each
        subsequent number is the sum of the previous two.
     (b) Write a non-recursive function to do the same
      (c) If your answer to part (i) involves binary recursion, consider the cost of this,
        and devise a recursive algorithm that uses linear recursion instead.
    5. Sorting, loop invariants and passing functions as parameters [**]
     Pseudo-code for a sorting function in matlab that can sort a set of inputs into
     ascending order is given below.
      (a) Determine the order O(:::) of the sorting routine
     (b) Determine a loop invariant for each loop and hence satisfy yourself that the
        function will have the desired effect
      (c) Explain how the sorting function can be made generic by replacing the
        comparison A[i] ¿ A[j] with a call to a function GreaterThan, which takes
        two items and returns 1 if x is less than y, and 0 otherwise, and where
        GreaterThan is a formal parameter to BubbleSort. Write down the likely
        function prototype for BubbleSort
     (d) Write such a comparison function that compares the lengths of two vectors
        under the 2-norm and show how it can be used with the generic sorting
        function to sort the rows of a matrix.
      Structured Programming MT2011                                                                             Page/3
             (e) Write two more comparison functions that use (i) the 1-norm and (ii) the
                  infinity norm
             (f) Comment on the advantages of this programming construct in this context.
                   1. ROUTINE: BubbleSort
                   2. INPUT: A is array of N elements
                   3. OUTPUT: A is sorted array of elements
                   4. for i=1 to N-1
                   5.    for j=i+1 to N
                   6.        if A[i]>A[j] then swap A[i] and A[j]
                   7.    endfor
                   8. endfor
                   9. return A
        6. Data structures: [**] The code below is an implementation in C of a linked
            list.
             (a) Write a function to insert an item at the start of the list
             (b) Write a function to append an item to the end of the list
             (c) Explain how to create a data structure with pointers to first and last ele-
                  ments in order to enable more efficient appending of a new element, and
                  modify your function PrependElement() and AppendElement() accord-
                  ingly
             (d) Explain how the data structure definition could be modified to create a
                  so-called “doubly-linked list” (i.e. in which each element links to both its
                  successor and predecessor.
                   /* Define list element container for Data */
                   struct list˙elt –
                        Data dat;
                        struct list˙elt *next;
                   ˝;
                   /* create a synonym for ”pointer to struct list˙elt */
                   typedef struct list˙elt *LinkedList;
                   /* Create a pointer to an empty list of Data items *
                   struct list˙elt *mylist=NULL;
                   /* or LinkedList mylist=NULL; */
        7. Simple algorithms on dynamic structures [**]
            Using one of the data structures from the previous question:
             (a) Write a function in order to split a sorted list into two after an element
                  whose value is specified by the value of an input parameter.
             (b) Write a function to merge two sorted lists into one.
             (c) The code below removes an item from a list. Work out what is wrong with
                  it and hence fix it.
   Structured Programming MT2011              Page/4
      /* Remove element from list */
      LinkedList RemoveElement(struct list˙elt* p)
      –
        return p-¿next;
      ˝
      /* Usage example: remove element pointed to by current-¿next */
      current-¿next = RemoveElement(current-¿next);
    8. Algorithms and loop invariants: [**]
     The method of bisection for finding the roots of a function f (x) is as follows:
     Starting with two points x1 and x2 in the domain of f :
       • Consider f (r) where r = (x1 + x2)=2
       • If f (r) close to zero return r
       • If signs of f (r) and f (x1) differ then look in [x1;r) otherwise look in (r;x2]
      (a) What are the preconditions and loop invariant required to implement this
        algorithm as a loop.
     (b) Hence (or otherwise) write a matlab function to implement it.
      (c) If the preconditions are not satisfied, what does your implementation do?
    9. Advanced Algorithms: [**]
     Anundirected graph can be represented in Matlab using a single matrix in which
     the (i,j)th entry in the matrix is the weight of the edge between nodes i and j,
     with a weight of zero meaning no edge exists (we assume that edges must have
     strictly positive weight).
     A spanning tree of a graph is a tree (i.e. every vertex can be reached from
     every other vertex via one and only one path) containing all the nodes of the
     graph. A minimal spanning tree of a graph is the panning tree whose sum of
     edge weights is minimal.
      (a) The matlab code below finds the minimal spanning tree of the input argu-
        ment graph using Prim’s algorithm
          http://en.wikipedia.org/wiki/Prim’s algorithm
        Read and understand the matlab code, and add comments where indicated
        that describe the meaning of each part of the code.
     (b) Write down the matrix G that represents the graph shown in the figure
        below.
      (c) Show an execution trace of the function running on this graph, clearly stat-
        ing the values of the variables at each starred location in the code.