Testing Novice Programmers

In 2004, a research paper titled "A Multi-National Study of Reading and Tracing Skills in Novice Programmers" was published which reported the results of a standardized written multiple-choice test given to several hundred university and college students who had just completed a first-year course in programming. This is essentially Question 8 from the test (the differences being you have to generate a random list of integers, you have a computer to test your solution, and you don't have the multiple choices).

Inversions

If any two numbers in a list of integers (not necessarily consecutive numbers in the list) are out of order, then that is called an inversion. For example, consider the list x that contains the following six integers:

4   5   6   2   1   3

There are 10 inversions in the list:

x.get(0) == 4   >   x.get(3) == 2
x.get(0) == 4   >   x.get(4) == 1
x.get(0) == 4   >   x.get(5) == 3 
x.get(1) == 5   >   x.get(3) == 2
x.get(1) == 5   >   x.get(4) == 1
x.get(1) == 5   >   x.get(5) == 3
x.get(2) == 6   >   x.get(3) == 2
x.get(2) == 6   >   x.get(4) == 1
x.get(2) == 6   >   x.get(5) == 3
x.get(3) == 2   >   x.get(4) == 1

Cut-and-paste the incomplete program given below into your editor, and fill in the for loops (shown in red) to complete a program that creates a list of N random integers and counts the number of inversions in the list (the first loop is identical to the first loop you wrote for Part 1 of the lab).

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Random;

public class InversionCount
{
   public static void main(String[] args)
   {
      PrintStream out = System.out;
       
      // N is the number of elements in the initial list
      final int N = Integer.parseInt(args[0]);

      // the list
      ArrayList<Integer> list = new ArrayList<Integer>();

      // add N random integers between 1 and MAX to the list
      final int MAX = 100;
      Random rng = new Random();
      for ()
      {
         
      }
      out.println(list);
      
      int inversionCount = 0;
      
      for ()
      {
         for ()
         {
            
            
            
            
         }
      }
      out.println(inversionCount + " inversions");
   }
}

Submit

Submit your program using the command:

submit 1020 L06 InversionCount.java

All done.