Steve Vickers: Introduction to Computer Science

Fundamentals of Computing: Introduction to Computer Science

Assessed coursework

This coursework is assessed for MSc students. You should deliver your answers to the box outside School reception by 12.00 midday on Monday 9th January 2012, the first day of spring term.

Intercalated year (ICY) students are advised to do the exercise as unassessed coursework, because it gives some preparation for the exam. If you would like me to mark your work to give feedback, post it in the same box as the MSc students, but please write "ICY" clearly at the top.

The exercise concerns a Java method to calculate integer square roots using the binary search algorithm.

By "integer square root" we mean the square root rounded down to an integer. Thus the integer square roots of 9 and 15 are both 3 (the actual square root of 15 is about 3.9).

Another way to think of this is that it is the largest integer s for which s*s <= n. Since it is the largest, we must have (s+1)*(s+1) > n.

Its Javadoc and method declaration are as follows.

    /** Integer square root
     * Calculates the integer part of the square root
     *   of n, i.e. integer s such that
     *   s*s <= n and (s+1)*(s+1) > n
     * 
     * @param n number to find the sqare root of
     * @return integer part of its square root
     * @throws IllegalArgumentException if n < 0
     */
    public static int intSqrt(int n){

You will find that the binary search algorithm as given in week 9 can be easily modified, using a test that compares the square of a number against n instead of comparing an array element against x. However, you have to be very careful about where to use < (strictly less that) or <= (less than or equal to. They are not quite the same as in the binary search in the notes.

At a certain point you will need to find m such that l < m <= r, given that l < r. Use m = (l+r+1)/2; for this.

  1. Write Java code for the method to calculate integer square root using the binary search algorithm. You must follow the Javadoc specification above exactly, including the exception throw, and you must use binary search. As described in the lectures, you should find it easiest to work out the answers for parts 1 and 2 together.
  2. Write down the loop invariant. Explain how various parts of your code match the loop invariant:

    (a) The final result is the correct answer.

    (b) The initialization establishes the invariant.

    (c) The loop body reestablishes the the invariant.

    (d) Progress is made on each iteration.

  3. Using javap, produce disassembled bytecode for your method and include it as part of your answer.
  4. For this part you may find it useful to consult the Java Virtual Machine Specification. Chapter 6 has a list of all the different instructions.

    (a) Which stackframe variables correspond to which parameters and locale variables in your Java source?

    (b) Which instructions in the bytecode correspond to which statements in your Java method?

    (c) For the Java statement m = (l+r+1)/2;, describe how the operand stack changes as the corresponding bytecode instructions are executed.

Feedback for exam

This exercise is designed to assess three kinds of knowledge and give you feedback on how well you are understanding the module topics.

  • Understanding of specification and loop invariants.
  • Familiarity with the binary search algorithm.
  • Understanding of how bytecode and the JVM work.

The exam will be in a similar style, covering all the topics of the module. You will be expected to have learned the algorithms covered in the module (in particular binary search and quick sort). You will not be expected to remember names of bytecode instructions - they will be provided if necessary.