Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Assignment 2 (value 10%)
Objectives
The objectives of this assignment are:
To demonstrate the ability to implement algorithms using basic data structures and operations on them.
To gain experience in designing an algorithm for a given problem description and implementing that
algorithm in Python.
To demonstrate an understanding of complexity, and to the ability to implement algorithms of a given
complexity.
Submission Procedure
1. Save your files into a zip file called yourStudentID yourFirstName yourLastName.zip
2. Submit your zip file containing your solution to Moodle.
3. Your assignment will not be accepted unless it is a readable zip file.
Important Note: You will be required to agree to these policies when you submit your assignment.
A common mistake students make is to use Google to find solutions to the questions. Once you have seen a
solution it is often difficult to come up with your own version. The best way to avoid making this mistake is
to avoid using Google. You have been given all the tools you need in workshops. If you find you are stuck, feel
free to ask for assistance on Moodle, ensuring that you do not post your code.
Marks: This assignment will be marked both by the correctness of your code and by an interview with
your lab demonstrator, to assess your understanding. This means that although the quality of your code
(commenting, decomposition, good variable names etc.) will not be marked directly, it will help to write clean
code so that it is easier for you to understand and explain.
This assignment has a total of 10 marks and contributes to 10% of your final mark. For each day an assignment
is late, the maximum achievable mark is reduced by 10% of the total. For example, if the assignment is late by
3 days (including weekends), the highest achievable mark is 70% of 10, which is 7. Assignments submitted 7
days after the due date will normally not be accepted.
Detailed marking guides can be found at the end of each task. Marks are subtracted when you are unable to
explain your code via a code walk-through in the assessment interview. Readable code is the basis of a
convincing code walk-through.
1
Task 1: Complexity (4 Marks)
Create a Python module called complexity.py. Within this module implement the following task. For this
module you may not use the Python built-in function pow(x) and you may not use the power operator **.
You may not import any other libraries or modules.
Part A: Peaks (2 Marks)
Sometimes in life we care more about finding peaks than we care about finding the maximum. For example,
during semester you know that the week containing the maximum amount of assessment is (probably) during
exam block. But you will also have weeks in which that particular week contains more assessment than the
week directly before it, or directly after it. As such, if you are planning on going to the movies with friends,
you should probably do it in a week that is not an assessment peak.
Write a function local peak(lst) that takes in a list of numbers, and returns the index of a local peak.
Input: a list lst containing two or more numbers, where no number is the same as its neighbour.
Output: an integer indicating the index of a local peak. If there is more than one peak in the given list, the
index of any peak may be returned. A peak is defined as a number that is greater than its neighbours. A
peak may be the first or last number in the list, in which case it must be greater than its only neighbour.
For full marks, this function must have a complexity of O(log(N)), where N is the length of lst. Be aware
that some Python functions have a higher complexity than you might think. One example is slicing, which has
a complexity of O(k) where k is the length of the slice.
Examples
a) Calling local peak([0,2,4,6,5,2]) returns 3.
b) Calling local peak([-7,-6,-2,-10,-5,-11]) returns either 2 or 4.
c) Calling local peak([8.8,8.6,8.1,8.2,8.1,8.01]) returns either 0 or 3.
Part B: Powers (2 Marks)
Write a function power(n, p) that takes a number and a power and returns the number raised to the given
power.
Input: a number n and a non-negative integer p.
Output: a number that is the evaluation of n
p
For full marks, this function must have a complexity of O(log(p)).
Examples
a) Calling power(2,8) returns 256.
Marking Guide (total 4 marks)
Marks are given for the correct behavior of the different functions:
(a) 1 mark for the correct behaviour of local peak, and 1 mark for implementing the function with a complexity
of O(log(N)). You must be able to explain why the function has a complexity of O(log(N)) to receive the
full mark.
(b) 1 mark for the correct behaviour of power, and 1 mark for implementing the function with a complexity
of O(log(p)). You must be able to explain why the function has a complexity of O(log(p)) to receive the
full mark.
Note: marks will be deducted for including in submitted module function calls that are outside of function
definitions, or print statements.