FIT2004- Assignment 1 Solved

PROGRAMMING CRITERIA: It is required that you implement this exercise strictly using the Python programming language (version should not be earlier than 3.5). This practical work will be marked on the time complexity, space complexity and functionality of your program, and your documentation.

Your program will be tested using automated test scripts. It is therefore critically important that you name your files and functions as specified in this document. If you do not, it will make your submission difficult to mark, and you will be penalised.


Learning Outcomes
This assignment achieves the Learning Outcomes of:

1) Analyse general problem solving strategies and algorithmic paradigms, and apply them to solving new problems;
2) Prove correctness of programs, analyse their space and time complexities;
4) Develop and implement algorithms to solve computational problems.
In addition, you will develop the following employability skills:

Text comprehension
Designing test cases
Ability to follow specifications precisely
Assignment timeline
In order to be successful in this assessment, the following steps are provided as a suggestion. This is an approach which will be useful to you both in future units, and in industry.

Planning
Read the assignment specification as soon as possible and write out a list of questions you have about it.
Clarify these questions. You can go to a consultation, talk to your tutor, discuss the tasks with friends or ask in the forums.
As soon as possible, start thinking about the problems in the assignment.It is strongly recommended that you do not write code until you have a solid feeling for how the problem works and how you will solve it.
Writing down small examples and solving them by hand is an excellent tool for coming to a better understanding of the problem.As you are doing this, you will also get a feel for the kinds of edge cases your code will have to deal with.
Write down a high level description of the algorithm you will use.
Determine the complexity of your algorithm idea, ensuring it meets the requirements.
Implementing
Think of test cases that you can use to check if your algorithm works.Use the edge cases you found during the previous phase to inspire your test cases.
It is also a good idea to generate large random test cases.
Sharing test cases is allowed, as it is not helping solve the assignment.
Code up your algorithm, (remember decomposition and comments) and test it on the tests you have thought of.
Try to break your code. Think of what kinds of inputs you could be presented with which your code might not be able to handle.Large inputs
Small inputs
Inputs with strange properties
What if everything is the same?
What if everything is different?
..
Before submission
Make sure that the input/output format of your code matches the specification.
Make sure your filenames match the specification.
Make sure your functions are named correctly and take the correct inputs.
Make sure you zip your files correctly (if required)
Documentation 
For this assignment (and all assignments in this unit) you are required to document and comment your code appropriately. This documentation/commenting must consist of (but is not limited to)

For each function, high level description of that function. This should be a one or two sentence explanation of what this function does. One good way of presenting this information is by specifying what the input to the function is, and what output the function produces (if appropriate)
For each function, the Big-O complexity of that function, in terms of the input. Make sure you specify what the variables involved in your complexity refer to. Remember that the complexity of a function includes the complexity of any function calls it makes.
Within functions, comments where appropriate. Generally speaking, you would comment complicated lines of code (which you should try to minimise) or a large block of code which performs a clear and distinct task (often blocks like this are good candidates to be their own functions!).
1             Integer Radix Sort 
Consider the Radix sort algorithm presented in lectures. As discussed in the second part of lecture 2, it is possible to vary the base used by this algorithm.

In this task you need to use radix sort to sort a given list of integers into ascending numerical order, using a given base. To do this, you will write a function num_rad_sort(nums, b).

There will be a video on moodle which discusses some concepts related to representing numbers in different bases. If you are confused about any aspect of this task, please watch the video!

1.1            Input
nums is a unsorted list of non-negative integers
b is an integer, with value ≥ 2
1.1.1       FAQ

Q: In what base will the input be given?

Q: When I write a list like [1,45,173] is this not in base 10?

Q: How can a number not have a base?

Q: In what base should we give out output?

Q: How does the parameter b affect the output?.

1.2            Output
num_rad_sort returns a list of integers. This list will contain exactly the same elements as nums, but sorted into ascending numerical order.

Example:

nums = [43, 101, 22, 27, 5, 50, 15]

>>>num_rad_sort(nums, 4)

[5, 15, 22, 27, 43, 50, 101]

1.3            Complexity
num_rad_sort should run in O((n + b)∗ logbM) time where

n is the length of nums
b is the value of b
M is the numerical value of the maximum element of nums