CS209 lab1

CS209 lab1

http://www.maths.nuigalway.ie/~gettrick/teach/cs209/l1.html

For this lab you should submit all source code (PYTHON files), and the result(s) of running the program on (a few) test cases. The source code must be well presented (indenting, spaces, reasonable variable/function names, etc.) and must include comments (as a rough guideline - aim to have nearly as many comments as lines of code).
The above material should be uploaded to BLACKBOARD before the deadline of 5pm Monday 1st. February 2016. You will lose 20% for each day (or part of day) the lab is late. (In BLACKBOARD, you should attach your PYTHON program under "Attach File" in the section "2. Assignment Materials". If you are including anything other than PYTHON code, e.g. answers to questions, etc, it can be cut/pasted in to "Submission" under "2. Assignment Materials".) If any of this is unclear, you should ask the Teaching Assistant in the lab.
Plagiarism (the unattributed copying of work from other sources (internet, fellow students,....)) will not be tolerated. Please see http://www.nuigalway.ie/plagiarism/. You risk getting zero for your lab if it is found to be plagiarized.

Study carefully the insertion sort algorithm and code (covered in letures), at https://www.khanacademy.org/computing/computer-science/algorithms/insertion-sort.

Study (and run) the program fcount.py at http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/. The purpose of that short simple program is to show you how you might use a counting variable to determine the number of times a function is called in a program. You should also study the other relevant programs at http://www.maths.nuigalway.ie/~gettrick/teach/cs209/progs/ such as binINSrec.py, nonBINinsREC.py, etc.

Write a program in PYTHON that carries out insertion sort. In each iteration, for the actual insertion, you must use a function. This can be modelled on functions covered in lectures - e.g. nonBINins(list,item) or nonBINinsREC(list,i,item).

Write a program in PYTHON that carries out binary insertion sort. In each iteration, for the actual insertion, you must use a recursive function.

Test both your programs on a random list of integers of length

50;
500;
5000.

(for this - you can use random.randrange() as described in the program shops1TIME.py). In each case, determine the number of times your function is called, and report these results when submitting your lab.