Scribd
Upload
12 views2 pages

Advanced Python Recursion Assignment

The assignment requires students to implement two recursive functions in Python: one to generate a sequence based on a natural number n that converges to 1, and another to compute n raised to the power of m efficiently. Submissions must include a Python file named assignment3.py and a separate PDF detailing the time complexity for the second question, if applicable. Plagiarism and cooperation are strictly prohibited, and all submissions must be made individually through Blackboard by the due date of April 20, 2025.

Uploaded by

nguyenthientruc.do
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views2 pages

Advanced Python Recursion Assignment

The assignment requires students to implement two recursive functions in Python: one to generate a sequence based on a natural number n that converges to 1, and another to compute n raised to the power of m efficiently. Submissions must include a Python file named assignment3.py and a separate PDF detailing the time complexity for the second question, if applicable. Plagiarism and cooperation are strictly prohibited, and all submissions must be made individually through Blackboard by the due date of April 20, 2025.

Uploaded by

nguyenthientruc.do
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Advanced Programming in Python

Assignment 3: Recursion

Due date is 20/04/2025 at 23:59

The assignment is strictly individual. Plagiarism and cooperation will be


thoroughly checked by hand, and by specialised software. Not only copying
other peoples code, but also giving your source code to other students will
be considered as fraud. Using solutions from the internet, even very small
portions are considered as plagiarism.
When we detect fraud, conform with the exam regulations (OER), we
will inform the exam comity, which will start a fraud process (see the OER).
Unfortunately, every academic year students get caught; we hope that this
will not be the case this year.

Questions
Implement the following programs in python:
1. Write a recursive function generate sequence, such that given a natural number n, it
returns the list [n1 , ..., nm ], where:

ˆ n1 = n,
ˆ nm = 1,
ˆ for every i < m, we have ni ̸= 1,
ˆ if ni is even, then ni+1 = ni /2, and
ˆ if ni is odd, then ni+1 = 3 ∗ ni + 1.

Thus, given n, if we keep updating n as follows: n = n/2 if n is even and n = 3 ∗ n + 1 for


n is odd. Our number will eventually converge to 1 irrespective of the choice of n. The
output function is the sequence of numbers generated until we converge to 1.

Example
Let n = n1 = 7. Since n1 is odd, we get n2 = 3 ∗ n1 + 1 = 22. Since n2 is even, we get
n3 = n2 /2 = 11. This should be repeated till we get 1.
Hence, generate sequence(n) returns [7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1].

2. Write a recursive function compute_power that takes two non-negative integers n and m
as inputs. The function computes the result of raising n to the power of m (i.e. n^m) in
an efficient way. The number of multiplications used in your implementation should be
in less than linear amount of multiplications. In other words, the time complexity of your
implementation should be strictly less than O(m).

1
Hint: n6 = n3 × n3 .
Note: You have to argue why your implementation has a time complexity of less than
O(m). Also, you are not allowed to use any predefined power operators.

Submission and Grading Criteria


First of all, do not solve the assignment in multiple python files. We expect from you
one pdf file (check second paragraph) and one python file that contains all the solutions of the
assignment’s questions. In case you are not solving all the questions, then make sure that you
also include the functions of the unsolved questions in your submission with pass in the body.
Moreover, your solution file must have the name [Link]; otherwise, the tests will not
run. Also, make sure that file begins with
"""
author : [ firstname lastname ]
studentnumber : [ your studentnumber ]
"""

Before the deadline make sure to submit both files through Blackboard. You should not submit
both files in a zip file, rather you have to upload both files individually through Blackboard.

Question 2 Time Complexity As mentioned in the second question, you have to determine
the time complexity of your implementation, and you need to argue why it is better than linear.
You have to do that in separate pdf file that you submit with the python file. The name of
the pdf file must be [Link]. In case you are not solving the part about the
complexity, you do not have to submit the pdf file.

Helper Functions You can define as many additional functions as you want. Help functions
should start with an underscore. But all solutions should not exceed 500 lines. In fact, 500 lines
is extremely generous bound. You need much less than that.

Grading The assignments are graded by both hand and unit tests. That means the results
of the functions should be precisely as expected by the given unit tests. Check the test file
test [Link] on Blackboard. Do not edit that file except for the imports if needed.
In grading we do not only look at functionality, but we also take code quality (including comments
in the code) into account.

Common questions

Powered by AI

Minor syntax errors can prevent test scripts from executing correctly, resulting in failed tests, which negatively impacts grading since functionality is a core criterion. Carefully resolving syntax issues ensures accurate evaluation of the solution logic and meets the requirement of correct execution stipulated in the assignment .

Including functions with 'pass' statements indicates that the student acknowledges the required functions but didn't implement them. This approach might be used to maintain structural completeness and avoid undefined function errors during testing. It also signals transparency about the uncompleted sections to the graders .

Analyzing time complexity is crucial because it ensures the function 'compute_power' runs efficiently, especially for large inputs. The complexity can be reduced below O(m) by utilizing an approach such as exponentiation by squaring. This method reduces the number of multiplications by computing n^m recursively as (n^(m/2) * n^(m/2)) if m is even, or n*(n^(m-1)/2 * n^(m-1)/2) if m is odd, thereby achieving a logarithmic time complexity of O(log m).

The 'generate sequence' function handles odd and even numbers by applying different transformations. If the number is even, it becomes half its value (n = n/2). If the number is odd, it undergoes the transformation n = 3*n + 1 . The sequence converges to 1 due to the properties of the algorithm, known as the Collatz Conjecture, which posits that this recursive transformation always reaches 1 irrespective of the starting integer .

Avoiding predefined power operators forces students to engage with the underlying mathematics of exponentiation, such as applying recursion or loops manually to devise an efficient algorithm. This exclusion promotes deeper understanding and skills in algorithm design and complexity management, which are critical in computer science education .

The submission requires a single Python file named assignment3.py, beginning with comments for author and student number . Additionally, if the time complexity is discussed, a separate PDF named Question2Complexity.pdf must be submitted. Both files must be uploaded individually to Blackboard without being zipped . Following these conventions ensures the test scripts function correctly and the assignment is graded accurately .

Helper functions starting with an underscore are allowed in the assignment to aid the primary functions without cluttering their logic. This allows for modular and readable code . There is no explicit limit on the number of these functions, as long as total line count stays under 500 and the functions support rather than overlap with the main task .

In Assignment 3, code quality is assessed based on readability, modularity, and proper in-code documentation in addition to functional correctness . This evaluation is integral as it encourages best coding practices, ensuring solutions are understandable and maintainable, which is essential for collaborative and long-term software development .

A complete submission for Assignment 3 must include a Python file named assignment3.py containing solutions to all questions, with unsolved functions using 'pass' . If the complexity of 'compute_power' is addressed, it requires a separate PDF file named Question2Complexity.pdf explaining why the implementation has a time complexity lower than O(m).

The plagiarism policy for Assignment 3 strictly prohibits copying from other students or the internet, as well as sharing one's code with others. Any detected plagiarism will initiate a fraud process in accordance with exam regulations, potentially leading to academic penalties . This policy underscores the importance of individual effort and originality in programming assignments .

You might also like