Steve Vickers: Introduction to Computer Science

Fundamentals of Computing: Introduction to Computer Science

Assessed coursework: solutions

See further down for feedback on general performance on coursework.

  1. Here is the code for the whole module.
  2. The loop invariant is 
            /* loop invariant
         * 0 <= l <= r <= n
         * l*l <= n
         * (r+1)*(r+1) > n
         */

    (a) When the loop test becomes false we have l >= r and so, from the loop invariant, we must have l == r. Using this, the loop invariant then also tells us that l*l <= n and (l+1)*(l+1) <= n and so l is the required answer.

    (b) Three conditions must be true when we replace l and r in the invariant by 0 and n. First, 0 <= 0 <= n <= n. This is true because in the case n < 0 we threw an exception. Second, 0*0 <= n. This is true for the same reason. Third, (n+1)*(n+1) > n. This is true because (n+1)*(n+1) >= 1*(n+1) == n+1 > n.

    (c) In the first case, when we update l to m and r is unchanged, we have checked that l*l <= n. Since m <= r, we have l <= r for the new l. In the second case we update r to m-1. Then for the new r we have (r+1)*(r+1) == m*m > n. Also, since l < m, we have l <= r for the new r.

    (d) From l < m <= r we see that either l strictly increases or r strictly decreases. Hence r-l strictly decreases. This is the measure of progress being made.

  3. public static int intSqrt(int);
  Code:
   0:   iload_0
   1:   ifge    12
   4:   new     #1; //class java/lang/IllegalArgumentException
   7:   dup
   8:   invokespecial   #2; //Method java/lang/IllegalArgumentException.""
:()V
   11:  athrow
   12:  iconst_0
   13:  istore_1
   14:  iload_0
   15:  istore_2
   16:  iload_1
   17:  iload_2
   18:  if_icmpge       48
   21:  iload_1
   22:  iload_2
   23:  iadd
   24:  iconst_1
   25:  iadd
   26:  iconst_2
   27:  idiv
   28:  istore_3
   29:  iload_3
   30:  iload_3
   31:  imul
   32:  iload_0
   33:  if_icmpgt       41
   36:  iload_3
   37:  istore_1
   38:  goto    45
   41:  iload_3
   42:  iconst_1
   43:  isub
   44:  istore_2
   45:  goto    16
   48:  iload_1
   49:  ireturn

  4. (a) The variables with indexes 0, 1, 2 and 3 are n, l, r and m respectively.

    (b) As follows:

    • 0,1: if (n < 0) (jump if n >= 0)
    • 4, 7, 8: create new exception object
    • 11: throw it
    • 12, 13 (here if n >= 0): l = 0;
    • 14, 15: r = n;
    • 16, 17, 18 (here for test on each iteration): while (l < r) (jump when l >= r)
    • 21 - 28: m = (l+r+1)/2;
    • 29 - 33: if (m*m <= n)
    • 36 - 38: l = m;
    • 41 - 45: r = m-1; (then jump back to loop test)
    • 48, 49: return l;

    (c) We are looking at lines 21 - 28, and show the stack after each instruction (top at right). 

      line  instruction  stack
   21:  iload_1      l
   22:  iload_2      l, r
   23:  iadd         l+r
   24:  iconst_1     l+r, 1
   25:  iadd         l+r+1
   26:  iconst_2     l+r+1, 2
   27:  idiv         (l+r+1)/2
   28:  istore_3     empty

Assessed coursework: feedback

Here is some feedback on how you managed with the coursework.

The marks were out of 20 for questions 1 and 2 together (7 for q. 1, 13 for q. 2) and 20 for questions 3 and 4 together (2 for q. 3, 18 for q. 4).

I tried to mark the questions as in an exam, where the pass mark would be 50% - i.e. 20 out of 40. Generally coursework marks are about 10% higher, because you have more time, access to books and so on. If your mark was less than 24 you should definitely be worrying about how to make sure you pass the module.

One thing to note is that a significant part was about loop invariants: 13 marks in q. 2. Also, in q. 1, 2 marks were for convincing me that the code worked properly. If the code matched the invariant you would get those 2 marks straight away, and if it didn't but the code was reasonably similar to the binary search in the notes you would get 1 mark.

I hope you are getting the message that they are a significant part of the module material and will be a significant part of the exam. Just as in the coursework, you are likely to be asked about invariants both in themselves and as part of discussing particular algorithms (e.g. binary search, quicksort).

The coursework was meant to give you some practice in using the idea of invariant in detail, so you could improve your understanding of how they work. A lot of you still need to work on this. When you get your marked work back you will see whether your understanding of invariants is good enough yet. Remember that there is a lot of material about loop invariants, including examples, in Reasoned Programming.

In the coursework, the basic questions about invariants you should ask yourself are these.

  • Do you understand that an invariant is condition, not code or pseudocode?
  • Do you understand the difference between the invariant and the loop test? (The loop test is the test carried out by the while loop to see if it is time to terminate yet).
  • Does your invariant carry enough information to tell you you have the right answer at the end? (This corresponds to question 2(a).)

Here are some other details about the marking.

  1. Question 1 was very explicit that you had to follow the specification in the Javadoc. Marks were deducted if you didn't do this. One example: you had to throw the exception as specified. Another: the specification of intSqrt said nothing about messages on System.out, and it is a mistake for intSqrt to produce any. Methods in the Java library don't send messages to System.out unless the API says very clearly that might happen.
  2. Some of you threw the exception in intSqrt and then caught it in intSqrt. This is pointless and not what the specification requires, and lost a mark.
  3. Some of you used an array to store all the integers from 0 to n. This is completely unnecessary and not a sensible way to write this binary search.
  4. Quite a few of you had an if or while test (!(m*m <= n && (m+1)*(m+1) > n)) making extra tests on each iteration. This is not necessary - see solutions. Usually it made it harder or impossible to see why the code would work.
  5. In question 4(c): for full marks you should show the contents of the operand stack after each instruction. On or two of you confused the operand stack with the stackframes.