1) A Java program that implements an insertion sort algorithm. (InsertionSort.java):

Must include the proper comments in the code.

2) A report in pdf. It contains:

a) the pseudocode of the insertion sort algorithm and assertions between lines of the algorithm.

b) As insertion sort has a nested-loop of two layers, you need to put one assertion in each loop.

c) a proof of the partial correctness of the algorithm using mathematical induction

c.1) prove the correctness of the two assertions you added in the previous question.

d) a theoretical analysis of the running time of the algorithm using big-Oh

Analyze the complexity of insertion sort algorithm using big-Oh. Briefly show how to derive the big-Oh notation in terms of the number of primitive operations.

e) an experimental analysis of the running time of the algorithm

You may write some codes to conduct the experiments. For example, you may randomly sample n elements, run the insertion sort program to sort these n elements in an ascending order, and calculate the time required. Different values of n should be used to conduct the experiments. Then you may plot a running time figure with respect to the input size n, and check whether it is consistent with your theoretical complexity analysis.